1

我的代码可以给出大多数素数，但它仍然包含 1 并遗漏了一些数字：23 和 47（在计算 100 以下的素数时）。出于某种原因，它包括 91，任何想法为什么？我一直在使用维基百科的阿特金筛子说明。

我的代码如下：

limit = 100
results = [2, 3, 5] #prime numbers
sieve = [i for i in range(limit + 1)] #numbers to test
TF = [False] * (limit + 1) #marks number as prime or not
ModFour = [1, 13, 17, 29, 37, 41, 49, 53]
ModSix = [7, 19, 31, 43]
ModTwelve = [11, 23, 47, 59]

for x in range(limit + 1):
    for y in range(limit + 1):
        test = 4 * x**2 + y**2 
        if test % 60 in ModFour:
            try:
                TF[test] = True
            except IndexError:
                pass 
        test = 3 * x**2 + y**2
        if test % 60 in ModSix:
            try:
                TF[test] = True
            except IndexError:
                pass 
        if x > y:
            test = 3 * x**2 - y**2
            if test % 60 in ModTwelve:
                try:
                    TF[test] = True         
                except IndexError:
                    pass 

for n in range(2, limit + 1):
    if TF[n] == True:
        for x in range((n**2), (limit + 1), (n**2)):
            TF[x] = False


for p in range(limit + 1):
    if TF[p] == True:
        results.append(sieve[p])


for prime in results:
    print prime

欢迎任何有关优化筛子的建议。谢谢

4

1 回答 1

1

您没有翻转TF[test]- 您只是将这些元素设置为True. 与（this SO question）的代码进行比较：

test = 4 * x**2 + y**2    | n = 4*x**2 + y**2
if test % 60 in ModFour:  | if n<=limit and (n%12==1 or n%12==5):
  try:                    |  
    TF[test] = True       |   is_prime[n] = not is_prime[n]
  except IndexError:      | 
    pass                  |

要删除1from results，只需在TF[5]构建results列表时开始：

for p in range(5, limit + 1):
    if TF[p] == True:
        results.append(sieve[p])
于 2015-01-30T00:52:47.000 回答