C++寻找下一个素数回文

Question

这是真正的问题

https://www.codechef.com/problems/PRPALIN/

以下代码适用于所有输入，但输入 900000 时执行时间为 1.125 秒。我如何优化代码？如何改进代码？

非常感谢任何帮助。谢谢你！ :)

#include <iostream>
#include <cmath>
#include <cassert>
#include <ctime>

clock_t start=clock();

long long a;

inline long long next_prime();
inline bool palindrome();


int main()
{
    freopen("in.txt","r",stdin);
    scanf("%ld", &a);
    assert(1 <= a <= 1000000);
    do
        a = next_prime();   
    while(!palindrome());
    printf("%ld\n",a);
    fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-start));

    return 0;
}

long long next_prime()
{
    long long num = a;
    num++;

    while(1)
    {
        int flag = 0;
        long long i;    
        long long z = sqrt(num);

        for(i = 2; i <= z; i++)
            if((num % i) == 0)
                flag = 1;       
        if(flag == 0)
            return num;
        else
        num++;
    } 
}

bool palindrome()
{
    long long reverse_num = 0;
    long long temp = a;
    while(temp != 0)
    {
        reverse_num = reverse_num * 10;
        reverse_num = reverse_num + temp % 10;
        temp = temp/10;
    }
    if(a == reverse_num)
       return true;
    else
       return false;
}

Answer 1

您可以使用以下算法优化检测质数函数。

创建一个从 2 到 n 的连续整数列表：(2, 3, 4, ..., n)。最初，让 p 等于 2，第一个质数。

从 p 开始，通过以 p 为增量计数到 n 来枚举它的倍数，并在列表中标记它们（这些将是 2p、3p、4p、...；p 本身不应被标记）。

找出列表中第一个大于p但未标记的数。如果没有这样的数字，停止。否则，令 p 现在等于这个新数（即下一个质数），并从步骤 3 开始重复。

检查此 link、http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes

至于回文检查，目前是O(n)，我想不出任何改进的方法。

C++寻找下一个素数回文

C++ Finding the next prime palindrome

c++

palindrome