为什么我的Atkin筛法实现会忽略接近指定极限的数字？

Question

我实现的Atkin筛法在接近极限的质数或合数方面存在一些问题，有些极限可以运行，而另一些则不行。我完全不知道问题出在哪里。

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

例如，当我使用Atkin筛法生成小于1000的质数时，它会漏掉997这个质数，但会包括965这个合数。但是如果我将极限增加到5000，它返回的列表就完全正确了。

- imperialdogma

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的索引向下移动一个来修复所有其他代码（例如，到处将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) 的下整数。此外，range(1,factor) 从1到factor-1。因此你需要减去1。

所以你需要将其更改为

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

请参考Steve Krenzel的另一个实现方式，查看如何更快地列出小于N的所有质数。

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

- unutbu

---

是的，在使用Java编程后，我注意到了所有这些错误...不过我一定会检查那个更快的实现。 - imperialdogma