3

我对阿特金筛法的实现要么忽略了接近极限的素数，要么忽略了接近极限的复合物。有些限制有效，有些则无效。我对出了什么问题感到完全困惑。

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 的限制，它返回的列表是完全正确的。

4

1 回答 1

6

  • 更改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] 从未使用过。因此，您可能认为更好的解决方法是 keep ，但通过将索引向下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

  • 由于 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
于 2010-03-08T02:43:56.407 回答