你好，所以我在做这个问题，他们给你的范围从最小 5 到最大 100,000,000
你必须找到从第一个数到第二个数的所有素数回文数
例子：
输入：5 500
输出：
5
7
11
101
131
151
181
191
313
353
373
383
因此，在您查看我的解决方案之前，您需要了解两件事，除了一些第一个素数之外，所有素数都以这 4 位数字 1、3、7、9 结尾，并且所有偶数位数的回文数都可以被 11 整除
所以理解这一点，你就知道所有的素数回文数都需要以这 4 位数字之一开头，并且没有偶数位数的素数回文数例如：7557
所以我的解决方案是创建回文并检查它们是否是素数，然后打印它们，我用来检查它们的方法是有一个像 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;
}
所以问题是为什么我的程序没有时间用完而他的程序没有，如果两者都做同样的事情，但我做的程序比他少？