파이썬 Atkin 체의 구현

Question

내 코드는 대부분 소수를 제공하지만 1은 여전히 ​​포함하고 일부 숫자는 누락됩니다 : 23 및 47 (100 미만의 소수를 계산할 때). 웬일인지 그것은 91를 포함한다, 어떤 생각? 다음 나는 Sieve of Atkin.

내 코드에 대한 위키 백과의 지침을 사용하고있는 것은 같이 체의 최적화에

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   

어떤 제안을 환영합니다. 감사합니다.

Answer 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     | 

이 results에서 1을 제거 results 목록을 만들 때 단지 TF[5]에서 시작하려면 :

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