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