Здравствуйте, я решал эту задачу, в которой вам дают диапазон от минимум 5 до максимум 100000000
, и вам нужно найти все простые палиндромы от первого числа до второго числа
пример:
ввод: 5 500
вывод:
5
7
11
101
131
151
181
191
313
353
373
383
Итак, прежде чем вы посмотрите на мое решение, вам нужно понять 2 вещи, что все простые числа, кроме некоторых из первых, заканчиваются этими 4 цифрами 1,3,7, 9 и что все палиндромы с четным числом цифр делятся на 11
, поэтому, понимая это, вы знаете, что все простые палиндромы должны начинаться с одной из этих 4 цифр и что не существует простых палиндромов с четным числом. Пример цифр: 7557
, поэтому я решил создать палиндромы и проверить, являются ли они простыми, а затем распечатать t их, и способ, которым я их проверял, заключался в том, чтобы иметь число вроде 12, а затем перевернуть его и добавить как 1221 и добавить число в центре от 1 до 9: 12121
но так, как я это сделал это было так, что все числа начинались с этих 4 цифр таким образом:
из 1-1 3-3 7-7 9-9
10-19 30-39 70-79 90 99
, и я делал это до тех пор, пока полученные числа не превысили предел, и в этом случае Я перестал создавать новые палиндромы, и хорошо в этом то, что я располагаю их по порядку
, создавая свое решение:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector < long long > vi;
typedef pair < long long, long long > pi;
typedef vector < pi > vpi;
ifstream fin("pprime.in");
ofstream fout("pprime.out");
int reverse2(int num, int middle) {
int i, save = num, digit, combino = 1;
for (i = 0; num; num /= 10) {
digit = num % 10;
i = 10 * i + digit;
combino *= 10;
}
return i + 10 * combino * save + combino * middle;
}
bool prime(int n) {
if (n <= 1)
return false;
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
bool solve(int i, int n, int m, int digits) {
int c, b;
c = reverse2(i, 0);
for (int j = 0; j <= 9; j++) {
b = c + j * digits;
if (b >= n && b <= m) {
if (prime(b)) {
fout << b << endl;
}
}
if (b > m) {
return 0;
}
}
return 1;
}
int main() {
int n, m;
fin >> n >> m;
if (5 >= n && 5 <= m) {
fout << 5 << endl;
}
if (7 >= n && 7 <= m) {
fout << 7 << endl;
}
if (11 >= n && 11 <= m) {
fout << 11 << endl;
}
int arr[4] = { 1,3,7,9};
bool b = 0;
int digits = 10;
while (!b) {
for (int j = 0; j < 4; j++) {
int s = arr[j];
int actualdigit = arr[j] * digits / 10;
for (int i = actualdigit; i < (actualdigit/ s) * (s + 1); i++) {
bool a = solve(i, n, m, digits);
if (!a) {
b = 1;
j = 20;
break;
}
}
}
digits *= 10;
}
return 0;
}
Проблема здесь в том, что у моего решения заканчивается время, например в данном случае: 9878210 9978210
, хотя использованная мной обратная функция была получена из другого решения, которое также решает проблему
код другого парня:
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
int primelist[100000];
int nprimes;
int isPrime(int num);
int reverse2(int i, int j);
int compare(const void *p, const void *q) { return *(int *)p-*(int *)q; }
void main (void) {
ifstream infile("pprime.in");
ofstream outfile("pprime.out");
int i, j, begin, end, num;
infile>>begin>>end;
if (begin <= 11 && 11 <=end)
primelist[nprimes++] = 11;
for (j = 0; j <= 999; j++)
for (i = 0; i <= 9; i++) {
num = reverse2(j,i);
if (num >= begin && num <=end && isPrime(num))
primelist[nprimes++] = num;
}
qsort(primelist, nprimes, sizeof(int), compare);
for (i = 0; i < nprimes; i++)
outfile << primelist[i] << "\n";
}
int
reverse2(int num, int middle) {
int i, save=num, digit, combino = 1;
for (i = 0; num; num /= 10) {
digit = num % 10;
i = 10 * i + digit;
combino *= 10;
}
return i+10*combino*save+combino*middle;
}
int isPrime(int num) {
int i;
if (num <= 3) return 1;
if (num%2 == 0 || num%3 ==0) return 0;
for (i = 5; i*i <= num; i++)
if (num %i ==0)
return 0;
return 1;
}
, поэтому Вопрос в том, почему у моей программы заканчивается время, а у него нет, если обе делают одно и то же, но я выполняю процедуру в меньшем количестве случаев, чем он?