# Determine all prime, palindrome string integers within a range

I have written a program in Python 3x to determine all the prime, palindrome string integers in the range of two given numbers.

from math import sqrt

def check_prime(n):
if n<2:
return False
for i in range(2,int(sqrt(n))+1):
if n%i == 0:
return False
else:
return True

for times in range(5):
a,b = map(int,input().split())
ct = 0
for n in range(a,b+1):
if str(n) == str(n)[::-1] and check_prime(n):
ct += 1
print(ct)


How can I make this program run faster, mainly optimizing my check_prime function so that it is faster than currently?

One suggestion: That sqrt is expensive, and you can eliminate it in a lot of common cases. For example: if any number except 2 is even, then it's not prime. Every second time you call check_prime, you're passing an even number.

So you can check n%2 before the loop, and eliminate that sqrt on half of your calls. You can extend this to check the first few primes explicitly, before starting your loop:

def check_prime(n):
if n<2:
return False
if n%2==0:
return n==2
if n%3==0:
return n==3
if n%5==0:
return n==5
for i in range(7, int(sqrt(n))+1, 2):
if n%i == 0:
return False
return True


You get diminishing returns by adding more checks. I benchmarked the above at about 2x as fast as your original code.

• Don't forget about Memoization (en.wikipedia.org/wiki/Memoization). That speeds up the code when you run it multiple times. You can even save the pre-computed values to a file and load it using eval. In php, it would be something like file_put_contents('primes.php','$primes='.var_export($primes)); to save and include 'primes.php'; or eval(file_get_contents('primes.php')); to load it. – Ismael Miguel Nov 28 '14 at 2:26
• shouldn't that be for i in range(7, int(sqrt(n)) + 1, 2) to skip even numbers? – Droogans Dec 18 '14 at 22:07
• @Droogans yes, that's a good idea. – Blorgbeard Dec 18 '14 at 22:11