关于#回文质数#的问题，如何解决？


#include <iostream>

using namespace std;

int f(int n){
    int t = 0;
    while(n != 0){
        t = t * 10 + n % 10;
        n /= 10;
    }
    return t;
}

bool p(int n){
    for(int i = 2;i < n;i ++){
        if(n % i == 0){
            return 0;
        }
    }
    return 1;
}    

int main(){
    long long a,b;
    cin >> a >> b;
    for(int i = a;i < b;i ++){
        if(f(i) == i && p(i)){
            cout << i << endl;
        }
    }
    return 0;
}

https://www.luogu.com.cn/problem/P1217
66分
SOS

回文判断有问题

【以下回答由 GPT 生成】

解决方案：

要解决这个问题并优化代码，可以采用以下步骤：

首先，我们可以优化质数判断的函数p。在当前代码中，对于每个数字n，我们都遍历从2到n-1的每个数进行取余运算，看是否有余数为0的情况。这种方法在处理大数时效率较低。但是我们可以观察到一个性质，即一个数n若不是质数，那么它的最小因子一定不会超过它的平方根。所以我们可以将循环条件改为i*i <= n，实现对数开方次数的循环即可。此外，还可以判断n是否为偶数，如果是偶数且不等于2，直接返回false，因为偶数不可能是质数。最后，需要注意的是n为1的情况，对于题目要求的回文质数，1不符合条件，所以在判断n为1时，直接返回false。

优化后的p函数代码如下：

cpp bool p(int n){ if (n == 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) { return false; } } return true; }

其次，优化回文数的判断函数f。在当前代码中，我们将数字n反转，并与原数字n进行比较，来判断是否为回文数。这种方法效率较低，可以采用另一种更高效的方法。我们可以将数字n转换为字符串保存，并使用双指针的方法来判断是否为回文字符串。即从字符串的两端开始，逐个比较字符是否相等，如果有不相等的情况则返回false，如果遍历到中间字符则返回true。

优化后的f函数代码如下：

cpp bool f(int n) { string s = to_string(n); int left = 0; int right = s.length() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; }

最后，对于区间[a, b)内的每个数字i，判断其是否是回文质数，并输出结果。我们可以将判断回文质数的条件由两个函数合并为一个条件判断，即同时判断是否为质数和是否为回文数。如果是回文质数，则直接输出该数字。

优化后的main函数代码如下：

cpp int main(){ long long a, b; cin >> a >> b; for(int i = a; i < b; i++){ if(p(i) && f(i)){ cout << i << endl; } } return 0; }

优化后的代码已经对质数判断和回文判断进行了优化，可以提高性能。请尝试使用优化后的代码进行提交，并观察是否有提高得分的情况。如果没有得到满分，可能还需要进一步优化算法。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

在原来的代码上修改，最后一个测试点好像是超时过不了；

通过搜索，找了一份代码可以通过所有测试点。

代码如下：

参考链接：

C/C++实现回文质数（超详解）-阿里云开发者社区题目链接题目描述输入样例题解部分完整代码未完待续参考文章

https://developer.aliyun.com/article/885856


#include<bits/stdc++.h>
#define N 100000010
using namespace std;
int p[N],t;
bool st[N];
void  get_prime(int n)
{
  for( int i=2;i<=n;i++)
  {
  if(i>10000000)
  continue;
  else
  {
    if(!st[i])p[t++]=i;
  for(int j=0;p[j]<=n/i;j++)
  {
    st[i*p[j]]=true;
    if(i%p[j]==0)break;
  }
  }  
  }  
}
int main()
{
  int i,j;
  int m,n;
  int a,b,c=0;
  scanf("%d%d",&m,&n);
  get_prime(n);
  for(i=0;i<t;i++)
  { 
  a=p[i];
  if(a<m)
  continue;
    c=0;
    while(a)
    {
    b=a%10;
    c=c*10+b;
    a/=10;
    }
    if(c==p[i])
    printf("%d\n",p[i]);
  }
  return 0;
}

你的回文和指数判断好像有点问题，看看这个Demo对你有没有帮助的

#include <iostream>
using namespace std;

int f(int n){
    int t = 0;
    while(n != 0){
        t = t * 10 + n % 10;
        n /= 10;
    }
    return t;
}

bool p(int n){
    for(int i = 2; i <= n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}    

int main(){
    long long a, b;
    cin >> a >> b;
    for(int i = a; i < b; i++){
        if(f(i) == i && p(i)){
            cout << i << endl;
        }
    }
    return 0;
}