为什么我执行的阿特金筛选数量接近指定的限制？

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

例如,当我生成质数达到1000的极限时,Atkin筛子错过了主要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)
  

  由于筛子[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
  

• 由于史蒂夫·克伦泽尔(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