Warum ist die Umsetzung des Sieb des Atkin mit Blick auf Zahlen an die angegebene Grenze schließen?

Question

Meine Implementierung von Sieb des Atkin entweder übersieht Primzahlen in der Nähe der Grenze oder Kompositen in der Nähe der Grenze . während einige Grenzen arbeiten und andere nicht. Ich bin völlig verwirrt darüber, was falsch ist.

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

Zum Beispiel, wenn ich einen Primzahlen bis an die Grenze von 1000 erzeugen, die Atkin Sieb verfehlt das prime 997, sondern schließt das Verbund 965. Aber wenn ich die Grenze von 5000 erzeugen auf, die Liste, um es zurückgibt, ist völlig richtig.

Answer 1

• Ändern lim zu limit. Natürlich müssen Sie das wissen müssen.
• Da sieve = [False]*limit, der größte Index erlaubt ist limit-1.

  Doch auf dieser Zeile

  if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
  

  Sie überprüfen, ob n<=limit. Wenn n==limit dann wirft sieve[n] einen Indexerror. Versuchen Sie Ihren Algorithmus mit einem kleinen Wert von limit (z n = 50). Sie werden diese Fehler sehen kommen. Eine einfache Lösung ist die Verwendung

  sieve = [False]*(limit+1)
  

  Die einfache Lösung ist ein bisschen verschwenderisch, da Sieb [0] nie verwendet wird. So können Sie eine bessere fix denken könnte, ist sieve = [False]*limit zu halten, aber fix alle anderen Code durch den Index auf sieve nach unten durch einen Schritt. (Zum Beispiel Änderung sieve[n] sieve[n-1] überall, etc.) Dies ist jedoch wird Sie zwingen, eine Reihe von zusätzlichen Subtraktionen zu tun, was gut nicht für die Geschwindigkeit sein. So ist die einfache / verschwenderisch Lösung ist eigentlich wahrscheinlich die bessere Option.

• Nach http: //en.wikipedia. org / wiki / Sieve_of_Atkin , x eine ganze Zahl ist in [1, sqrt (limit)], einschließlich der Endpunkte sein.

  In Ihrem Code

  factor = int(math.sqrt(limit))
  

  und int nimmt den Boden von math.sqrt(limit). Des Weiteren

  range(1,factor) geht von 1 bis Faktor-1. So können Sie von 1.

  sind aus

  Sie müssen also diese zu

  ändern

  factor = int(math.sqrt(limit))+1
  

• Sehen schnellster Weg, um alle Primzahlen zur Liste unter N für eine alternative (und schneller) Umsetzung des Siebs des Atkin, wegen 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