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

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 下降了一位。（例如，改变 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 到因子 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