using namespace std;
int main()
{
int a, rev = 0, c = 0,temp,i;
cin>>a
;
for(; c=0; a++)
{
int b = sqrt(a);
for(i = 2; i<=b; i++)
{
if((a%i)!=0)
{
temp=a;
while(temp!=0)
{
int r = temp%10;
rev = rev*10 + r ;
temp = temp/10;
}
}
if(rev == a)
{
cout<<rev<<"\n";
c=1;
}
}
}
return 0 ;
}
I can’t figure out what is wrong with the answer.?
#include <math.h>
using namespace std;
int main()
{
int a, rev = 0, c = 0,temp,i;
cin>>a;
for(; c=0; a++)
{
int b = sqrt(a);
for(i = 2; i<=b; i++)
{
if((a%i)!=0)
{
temp=a;
while(temp!=0)
{
int r = temp%10;
rev = rev*10 + r ;
temp = temp/10;
}
}
if(rev == a)
{
cout<<rev<<"\n";
c=1;
}
}
}
return 0 ;
}
You need to make a few changes in the solution, because finding that, if a number is prime or not takes more time than checking for palindrome.
First check for palindrome and if the number is palindrome then check for prime.
Use this algorithm:
n=input()
for(i=n;;i++)
{
temp=i;
If (temp is palindrome)
{
check if i is prime
}
If(i is prime and palin)
break;
}
print i;
Here is my solution using the above algorithm,
http://www.codechef.com/viewsolution/4174377
If you still have any problem you can comment below
The reason why we are implementing palindrome testing before palindrome testing before primality testing is : the total no of palindromes between 1 to 10^6 is less than 2000 whereas the no of primes is much larger.also palindrome checking can be implented with O(1) algorithm whereas time complexity of primality testing is higher.
An even faster way than the above given solution would be to just generate the palindromes>=n,(instead of incrementing by one),and check if any of them are prime ,break away from the loop when you encounter such a palindrome.
It can also be optimized further. Generate all the primes till 1030000. Now for checking that a number is prime or not, there is no need to divide by all numbers till sqrt(n). You only need to divide by all the primes<=sqrt(n) and also use the fact that if(n>98689) the prime palin would be 1003001. This will get you an AC in 0.00 
http://www.codechef.com/viewsolution/4374996
Happy Coding!
But there is no need to generate all the primes till 1030000,generating all the primes till 1100 would be enough because sqrt(1003001)<1100.this will further reduce the no of operations.CHEERS:)
thanks I got it!!
srry for the above comment…it seems that you have mistyped as 1030000 but your code calculates correctly till sqrt(1003001) only.But i already know of such a approach,but what i actually wanted to say was instead of incrementing by 1 ,we should straight away find the next palindrome if the current palindrome is not a prime.
Sorry, yes typed it wrongly, it is actually till sqrt(1030000) as you saw in the code. Thanks for pointing it out.
I saw your code. It is still 0.07 execution time. Now try to implement the optimization for primes in your code and the execution time will reduce to 0.00
Also use the fact that if(n>98689) ans=1003001
I generate the primes only when n<=98689 and then find the answer for n, there is no need to generate when n>98689
Use your optimization also. But there is a need for the optimization of prime testing method also.Then only the execution time will be 0.00
Happy Coding
i accept that optimization is needed in the prime generation part to a great extent,…it is the main thing that takes up time in the whole code…i had just not implemented it in my code (though i knew it could be done this way),that was my fault 