为什么我的阿特金筛法实现忽略了接近指定极限的数字？

Question

我实现的阿特金筛法在处理接近上限的素数或者合数时，总是出问题。有些上限能正常工作，有些却不行。我对此感到非常困惑，不知道哪里出了错。

def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
    for j in range(1, factor):
        n = 4*i**2+j**2
        if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
            sieve[n] = not sieve[n]
        n = 3*i**2+j**2
        if (n <= lim) and (n % 12 == 7):
            sieve[n] = not sieve[n]
        if i>j:
            n = 3*i**2-j**2
            if (n <= lim) and (n % 12 == 11):
                sieve[n] = not sieve[n]
for index in range(5,factor):
    if sieve[index]:
        for jndex in range(index**2, limit, index**2):
            sieve[jndex] = False
for index in range(7,limit):
    if sieve[index]:
        results.append(index)
return results

比如，当我生成到1000的素数时，阿特金筛法漏掉了素数997，却把合数965算进去了。但是如果我把上限设到5000，返回的列表就完全正确了。

Answer 1

• 把 lim 改成 limit。当然你应该知道这一点。
• 因为 sieve = [False]*limit，所以最大的索引是 limit-1。

但是，在这一行

if (n <= limit) and (n % 12 == 1 or n % 12 == 5):

你在检查 n<=limit。如果 n==limit，那么 sieve[n] 会引发一个索引错误（IndexError）。试试用一个小的 limit 值（比如 n=50）来运行你的算法。你会看到这个错误出现。一个简单的解决办法是使用

sieve = [False]*(limit+1)

这个简单的解决办法有点浪费，因为 sieve[0] 从来没有被用到。所以你可能会觉得更好的办法是保持 sieve = [False]*limit，但把你其他代码中的索引都减一。（例如，把 sieve[n] 改成 sieve[n-1]，等等。）但是，这样会让你做很多额外的减法，这对速度不好。所以这个简单/浪费的解决办法其实可能是更好的选择。

根据 http://en.wikipedia.org/wiki/Sieve_of_Atkin，x 应该是一个在 [1,sqrt(limit)] 范围内的整数，包括端点。

在你的代码中

factor = int(math.sqrt(limit))

而 int 会取 math.sqrt(limit) 的下限值（floor）。此外，

range(1,factor) 是从 1 到 factor-1。所以你少了 1。

所以你需要把这个改成

factor = int(math.sqrt(limit))+1

查看 列出所有小于 N 的素数的最快方法，这是 Steve Krenzel 提供的一个替代（更快的）阿特金筛法实现。

def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results