Prime Palindrome HELP Part 3-Time Exceeded

I’ve optimized the prime function and its still exceeding the time limit? Any ideas?
Solution located at : http://www.codechef.com/viewsolution/3901718

Your solution is of complexity O(n*sqrt(n)) and n can go up to 10^6, thus your solution exceeds time limit.

Since the number of prime palindromes, less than or equal to 1000000 is not very huge, you can preprocess it on your local machine and use it in your solution. (That has been done by most of the users with fastest execution times for that question).

One optimization that you can try is storing all primes using a sieve and then checking for the palindromes.

1 Like

Checking prime function takes too much time.

Try checking isprime only if the number is a palindrome.

if(ispalindrome(m))
  if(isprime(m))
    print m
2 Likes

Here is your accepted solution
http://www.codechef.com/viewsolution/3901791