Trying to find the next prime number

[deanhystad]

I added Pedroski55's heuristic to is_prime().

def is_prime(x):
    # Check if x in small primes or in range of small primes
    if x in small_primes:
        return True
    if x < small_primes[-1]:
        return False

    # Check if x ends in digit that is divisible by 2 or 5
    if x % 10 not in (1, 3, 7, 9):
        return False

    # All non-prime numbers have a prime factor.  Check if
    # any of the small primes are a factor of x.
    nmax = int(x**0.5) + 1
    for n in small_primes:
        if n > nmax:
            return True
        if x % n == 0:
            return False

    # Brute force it the rest of the way.
    for n in range(211, nmax, 2):
        if x % n == 0:
            return False
    return True

I was surprised to find that this actually increases the number of modulo divisions by 10% I had to run the tests several times using different approaches to convince myself that this was true. I suppose that there are so many numbers not divisible by 2 or 5 that testing these numbers twice is inefficient.

I removed 2 and 5 from the list of small primes to prevent them being tested twice and repeated my tests. Now Pedroski55's heuristic is a 5% improvement over using the complete set of small primes.