一级筛/一对在一个范围内

Question

我正在尝试编写一个素数筛生成器，我将其转换为打印列表，然后在给定范围内打印素数。我很确定我的配对数是正确的，但出于某种原因，我在素数列表中得到了一些非素数的额外值。（我马上发现了这一点，因为我在输出中的最后一个值是3599，这不是素数）。我不确定我是否有某种逻辑错误，所以任何帮助都很棒。

def sieve(n):
     a = [True] * (n)
     a[0] = a[1] = False
     for (i, isPrime) in enumerate(a):
         if isPrime:
              yield i
             for n in range(i*i, n, i):
                 a[n] = False


 def pairs(li):
     pair = 0
     for i, x in enumerate(li):
         if i < len(li)-1:
             if li[i] + 2 == li[i+1]:
                 pair += 1
     return pair

 p_3600 = list(sieve(3600))

 ans = [vals for vals in p_3600 if vals > 1600]

 print ans

 print "pairs:", pairs(ans)

Answer 1

您的筛选功能不正确。您将所有数字标记为非素数，从“2”开始。你需要从素数的下一个倍数开始，即prime*prime

因此，你必须从i * i而不是i开始（我使用了i * 2，它有效但冗余，因为当i==2时已经被第一个循环覆盖）

def sieve(n):
    a = [True] * n
    a[0] = a[1] = False
    for (i, isPrime) in enumerate(a):
     if isPrime:
        yield i
        for j in range(i*i, n, i):
            a[j] = False

为了测试你的列表，我建议你添加一个质数测试，这样你就可以确定：

# make sure it works: time-costly but reassuring
import math
for i in ans:
    si = int(math.sqrt(i))+1
    for j in range(2,si):
        if i%j==0:
            raise Exception("%d is not prime (%d)" % (i,j))