Python 比素数列表更快的替代方法？

Question

我需要找到指定范围内的第一对素数，这些素数之间必须有一定的差异，并且在该差异内没有其他素数。我的代码似乎可以正常工作，但速度慢得令人痛苦——我想是因为我使用列表来处理素数。什么是更好的方法？

g=difference;
n=first number in range
m= second number in range

def gap(g,n,m):

    prime_list = []
    for num in range(n,m+1):
         if all(num%i!=0 for i in range(2,int(num**0.5)+1)):
                prime_list.append(num)

    if len(prime_list)<1:
        return None

    for pnum in prime_list:
        for index in range(len(prime_list)):
            pnum2 = prime_list[index]
            diff = abs(pnum - pnum2)

            if diff == g:

                checker = abs(prime_list.index(pnum2) - prime_list.index(pnum))
                if checker <=1:
                   return [pnum, pnum2]

Some tests:
    Test.assert_equals(gap(2,100,110), [101, 103])
    Test.assert_equals(gap(4,100,110), [103, 107])
    Test.assert_equals(gap(2, 10000000, 11000000), [10000139, 10000141])

Answer 1

为什么要将素数存储在 list 中？你一次只需要记住一个。您将按升序处理它们，正如 jasonharper 指出的那样，您需要做的就是在遇到第一个等于连续素数之间的 g 的增量时停止：

def gap(g, n, m):
    previous_prime = None
    for candidate in range(n, m + 1):
        if all(candidate % factor for factor in range(2, int(candidate ** 0.5) + 1)):
            if previous_prime is not None and candidate - previous_prime == g:
                return [previous_prime, candidate]
            previous_prime = candidate

Python 比素数列表更快的替代方法？

Python's faster alternative to lists for prime numbers?

primes

list

python-2.7