5
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ismael Miguel Nov 28 '14 at 2:26
  • 1
    \$\begingroup\$ shouldn't that be for i in range(7, int(sqrt(n)) + 1, 2) to skip even numbers? \$\endgroup\$ – Droogans Dec 18 '14 at 22:07
  • \$\begingroup\$ @Droogans yes, that's a good idea. \$\endgroup\$ – Blorgbeard Dec 18 '14 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.