Finding the first pair of prime numbers that have some specified difference

Question

I tried printing the first pair of prime number in between a list of numbers with a particular difference. But my run time is still too high (for large range of numbers). I want to reduce the run time by using any method from standard library like itertools.

def prime(x):
    """To generate prime number"""
    a = x // 2 + 1
    for i in range(2, x):
        if x % i == 0:
            return False
        elif i == a:
            return True


def gap(p, q, m):
    """To generate gap in between two prime numbers"""
"""p is the difference,q is the lower limit where the list of numbers in between which prime is filtered,m is the upper limit"""
    b = []
    a = b.append
    c = prime
    q = (q // 2) * 2 + 1
    for i in range(q, m + 1, 2):
        if c(i) == True:
            a(i)
            if len(b) > 1:
                if b[-1] - b[-2] == p:
                    return [b[-2], b[-1]]

Answer 1

First thing first, get rid of these ugly a and c. They do not add any value, but only obfuscate the code.

def gap(p, q, m):
    """To generate gap in between two prime numbers"""
"""p is the difference,q is the lower limit where the list of numbers in between which prime is filtered,m is the upper limit"""
    b = []
    q = (q // 2) * 2 + 1
    for i in range(q, m + 1, 2):
        if prime(i):
            b.append(i)
            if len(b) > 1:
                if b[-1] - b[-2] == p:
                    return [b[-2], b[-1]]

Notice that I also removed a redundant == True.

Second, you don't need to keep the entire list of primes. You are only interested in the last two of them. Consider

def gap(p, q, m):
    b = find_first_prime_after(q)
    for i in range(b + 2, m + 1, 2):
        if prime(i):
            if i - b == p:
                return b, i
            b = i

Finally, your primality test is very suboptimal. Implementing the sieve would give you a boost.

Answer 2

The most basic method of checking the primality of a given integer n is called trial division. This method divides n by each integer from 2 up to the square root of n. Any such integer dividing n evenly establishes n as composite; otherwise it is prime. Integers larger than the square root do not need to be checked because, whenever n=a * b, one of the two factors a and b is less than or equal to the square root of n. Another optimization is to check only primes as factors in this range. For instance, to check whether 37 is prime, this method divides it by the primes in the range from \$2\ to\ √37\$, which are \$2, 3,\ and\ 5\$. Each division produces a nonzero remainder, so 37 is indeed prime (from wikipedia).

import math
def prime(x):
    r = int(math.sqrt(x))
    for i in range(2, r + 1):
        if x % i == 0:
            return False
    return True

Answer 3

Depending on how large your lower and upper limits are, it may be faster to just generate all primes using a Sieve of Eratosthenes implementation.

If the limits are beyond what is reasonable to generate all primes for, then primality testing such as Miller-Rabin is significantly faster than trial division. For example, gmpy2.is_prime.

Answer 4

You ask for speed up, so let's get timing data for the version you posted. I've appended this to your code

from timeit import default_timer as timer
args = (2, 1234567, 2345678)
print(args)
foo = gap(*args)

def timedGap():
    start = timer()
    gap(*args)
    end = timer()
    return end-start

(timedGap() for dummy in range(1, 3))
timings = tuple((timedGap() for dummy in range(1, 10)))
print( ( min(timings), sum(timings)/len(timings),  max(timings) ) )
print(foo)

This is configured to search for a pair of twin primes in the range [ 1 234 567, 2 345 678 ]. It prints the arguments to gap(), then runs gap() once to get the result, stored in foo. Then runs timedGap() three times, discarding the timing data, in an attempt to do whatever priming is possible. Then runs timedGap() ten times to gather run time statistics. What is reported is (minimal time, average time, and maximal time) then the contents of foo.

On my hardware, your code produces the following output (with timings truncated to milliseconds for readability).

(2, 1234567, 2345678)
(0.889..., 0.928..., 0.956...)
[1234757, 1234759]

The same timing protocol is used subsequently.

First, a prime is 2, 3, congruent to 1 modulo 6 or congruent to 5 modulo 6. (Proof 1) So in prime(x), you should only be testing one-third of range(2,x). Also, the smallest prime divisor of a composite number is no greater than the square root of that number. (Proof 2) This means we can rewrite prime(x) as follows.

from math import sqrt, floor
def prime(x):
    """Test that x is a prime number.  Requires x is a positive integer."""
    if not( (x > 0) and isinstance(x, int) ):
        raise ValueError("x must be a positive integer.")
    # Note that the original prime() incorrect returns nothing when passed 1 as input.  Let's fix that.
    # 1 is not prime.
    if (x == 1):
        return False
    # We check 2, 3, AND 5 explicitly so that we can start the subsequent range at 6.
    # Note that this leaves only (1/2)(2/3)(4/5) = 4/15 ~= 25% of integers to check further.
    if (x == 2) or (x == 3) or (x == 5):
        return True
    if (x % 2 == 0) or (x % 3 == 0) or (x % 5 == 0):
        return False
    # Rather than alternately increment by 2 and 4, test twice per block of 6.
    for i in range(6, floor(sqrt(x)) + 1, 6):
        if x %(i+1) == 0:
            return False
        if x %(i+5) == 0:
            return False
    return True

and timing (truncated at microseconds):

(2, 1234567, 2345678)
(0.000657..., 0.000676..., 0.000729...)
[1234757, 1234759]

so that's more than 1000-times faster.

We could replace the checks with x % 2, x % 3, and x % 5, with math.gcd(x,30) > 1, but this doesn't save enough time to bother.

I don't have time to improve your gap(), but here are some comments/observations.

We already know that all primes except 2 and 3 are congruent to 1 or 5 modulo 6, so the only possible prime gaps start at 2 and have odd length, start at 3 and have even length, or start at a prime congruent to 1 or 5 modulo 6 and have length congruent to 5-5=0, 5-1=4, 1-5=2, or 1-1=0 modulo 6. (And the collection of integers that are congruent to 0, 2, or 4 modulo 6 is the even integers.) This should allow us to reject impossible ps much faster.

(A brief style comment: p and q are common labels for prime numbers and m is a common label for an integer. Much better argument names for gap() are start, end, and gapSize.)

Observations:

• The list of primes less than the least potential member of a sought pair are of no use to us, so retaining them (and modifying a list of them) is a waste of time and space.
• We only need to iterate through potential least members of the pair to find the first pair and we can stop as soon as the second member would be outside of the search range.
• So let i be the potential first prime in the pair and have it range from q to m - p, only taking values where i and i + p are congruent to 1s and 5s modulo 6. (For instance, if p is 2, then the least member must be congruent to 5 modulo 6 and the greater member is automatically congruent to 1 modulo 6.)

Proof 1:

An integer, N, is congruent to a modulo 6 if there is an integer k such that N == a+6k.

• If N is congruent to 0 modulo 6 then N = 0 + 6k and 6 divides N, so N is not prime.
• If N is congruent to 2 modulo 6 then N = 2 + 6k = 2(1+3k) and 2 divides N, so either N = 2 or N is not prime.
• If N is congruent to 3 modulo 6 then N = 3 + 6k = 3(1+2k) and 3 divides N, so either N = 3 or N is not prime.
• If N is congruent to 4 modulo 6 then N = 4 + 6k = 2(2+3k) and 2 divides N, so N is not prime. (We can skip "N = 2" as a possibility because 2+3k can never be 1.)

We have found that for N to be prime, either N = 2, N = 3, N is congruent to 1 modulo 6, or N is congruent to 5 modulo 6.

Proof 2:

Suppose that N is a composite number, so that it has at least two prime divisors. Assume further that all the prime divisors are greater than the square root of N. This is a contradiction. Call the two smallest prime divisors of N by the names p and q. Note that p > sqrt(N) and q > sqrt(N) and that pq is a divisor of N so is no greater than N. But, pq > sqrt(N)sqrt(N) = N, which is a contradiction. Therefore, any composite integer has a prime divisor no greater than its square root.