素数に対するリストの代わりに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に保存するのですか？一度に1つだけ覚えておく必要があります。 jasonharperが指摘するようにあなたは、あなたがする必要があるすべてはあなたが連続した素数の間gに等しい第1のデルタが発生したときに停止され、昇順にそれらを介して働くとされます：

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