# Prime Palindrome

My code is not working can someone plz suggest some changes in it.My code is

#include
#include
#include<math.h>
using namespace std;
int isprime(int);
int palin(int);
int main()
{
long int N;
cin>>N;
while(N)
{
if(isprime(N))
{
if(palin(N))
{
cout<<N;
break;
}

``````   }
N++;
``````

}
}
int isprime( int n)
{ int i;
for(i=2;i<=n/2;i++)
{
if(n%i==0)
return 0;
}
if(i>n/2)
return 1;
}
int palin(int N)
{
int i=0,cnt,j,n;
int M,K=0;

``````M=N;
while(N)
{
N=N/10;
i++;
}
N=M;
while(N)
{
j=N%10;
K=K+(pow(10,i)*j);
i--;
N=N/10;
}
if(M==K)
return 1;
else
return 0;
``````

}

Why are you using the 2 while loops for checking if a number is a palindrome.

Here, it can be done in 1 loop,

``````int palin(int n)
{
int c,r=0;
c=n;
while(c>0)
{
r=r*10+c%10;
c=c/10;
}
if(r==n)
return 1;
else
return 0;
}
``````

After correcting this also you are not going to get correct answer, you need to optimize the code.

Now, use this algorithm:

First generate all primes till sqrt(1030000) (And try to use an efficient algorithm for this)

for(i=n;;i++)

{

temp=i;

Check if temp is palindrome

If (temp is palindrome)

{

check if i is prime

//For checking i as prime divide with all primes till the sqrt(i)( no need to divide with all numbers
//till number/2 )

}

If(i is prime and palin)

break;

}

print i;

**Use a good method to generate primes.**
1 Like

2 changes I would like to suggest . for finding prime numbers instead to going through n/2 numbers use this
Int isprime(int n){
For (int I=2;I<=(int)sqrt(n);I++)
If(n%i==0)
Return 0;
Return 1;
}
And second .first check if the number is palindrome or not .because no of palindromes are << no of primes. I.e chances of numbers being a palindrome is less than chances of number being prime
If(Palin(int n))
If (isprime(int n))
Check my code if any doubt

Check out this discussion, also on the same question.

http://discuss.codechef.com/questions/46255/prime-palindromeplzzz-tell-me-whats-wrong-with-my-code

In the second answer, I have posted a good method to generate primes.

this method for checking a number as prime is not fast.
It will also generate time limit exceed.

You need to use some improvisation, for this method to work.
Calculate the largest palindrome less than 1000000, then it should work, and create a separate case for all numbers greater than that number.We can also find more long intervals between prime palins and also put them in separate conditions.

Actually this passes the time limit .I did this question using this . although precomputation would be better than checking each element

You will need this palindrome number for that 98689 and improvise a bit.
Now try to run it without this condition and use this approach, dividing by every number till sqrt(n) for checking primes, see what happens.

I understood your point and tried without taking any special case such as 98689 and it still passed

``````
[1]

[1]: http://www.codechef.com/viewsolution/4174354``````

Splendid!
My only aim was to share that the question can we further optimized

Check out the last three solution and specially the one with execution time 0.01 sec.
These optimizations and prime generation methods are very useful, some questions have tight constraints and time limits.

Happy coding!
Cheers!

This is elegant. 0.01 is far better than 0.35 . happy coding .nice solution btw

Thanks a lot man.It worked easily but i want to ask whether hardwired coding approach where prime array is predefined in ur program is recommended or not?

Thanks man it helped me a lot.

No, I would never recommend it.

Besides, the time limit of such questions where prime numbers array is required also includes the time for generating primes or any other precomputation for that matter.