C++ Finding the next prime palindrome

Question

Here's the actual question

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

The following code works well on all inputs but on input of 900000 the execution time is 1.125sec. How do I optimize the code? How can the code be improved?

Any help is greatly appreciated. Thank You! :)

#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;
}

you probably will get better results with this question at http://codereview.stackexchange.com/ c: — Rod, Jul 29 '15 at 18:08
Also, [this answer](http://stackoverflow.com/a/8187788/509868) might be helpful — anatolyg, Jul 29 '15 at 18:10

score 3 · Accepted Answer · answered Jul 29 '15 at 18:13

You can optimize the detecting prime function by using the following algorithm.

Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n). Initially, let p equal 2, the first prime number.

Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked).

Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Check this link, http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes

As for the palindrome check, it's currently O(n), I can't think of any way to improve upon that.

C++ Finding the next prime palindrome

1 Answers1