Meine Implementierung des Eratosthenes-Siebs ist fehlerhaft?

Question

Ich mache eine Sieve of Eratosthenes-Implementierung in Python. Ein Problem, das auftritt, ist, dass nicht alle Primzahlen auftreten (hauptsächlich die mit der niedrigeren Nummer).

Hier ist mein Code:

def prevPrimes(n):
    from math import sqrt
    from time import time
    start = time()
    if type(n) != int and type(n) != long:
        raise TypeError("Arg (n) must be of <type 'int'> or <type 'long'>")
    if n <= 2:
        raise ValueError("Arg (n) must be at least 2")
    limit, x, num, primes = sqrt(n), 2, {}, []
    for i in range(1, n+1):
        num[i] = True
    while x < limit:
        for i in num:
            if i%x==0:
                num[i] = False
        x += 1
    for i in num:
        if num[i]:
            primes.append(i)
    end = time()
    primes = sorted(primes)
    print round((end - start), 2), ' seconds'
    return primes

Wenn ich >>> prevPrimes(1000) eingebe, würde ich erwarten, dass das Ergebnis wie folgt beginnt: [2, 3, 5, 7, 11, 13, 17] usw. So sieht es jedoch aus: [1, 37, 41, 43, 47, #more numbers].

Ich weiß, dass das Problem in der Tatsache liegt, dass die "ursprünglichen" Primzahlen (2, 3, 5, 7, 11, 13, 17 usw.) aufgrund der Art und Weise, wie mein Programm prüft, als False angegeben werden die Primzahlen. Wie kann ich das vermeiden? Danke im Voraus :)

python function primes sieve

0

Rushy Panchal 21 Nov. 2012 im 09:25

Answer 1

Das war also keine tatsächliche SoE-Implementierung, eine, die ich vor einiger Zeit geschrieben habe, ist unten aufgeführt.

number_primes = 10
prime_list = [True]*number_primes

for i in range (2, number_primes):    #check from 2 upwards
  if prime_list[i]:                   #If not prime, don't need to bother about searching
    j = 2
    while j*i < number_primes:        # Filter out all factors of i (2...n * prime)
      prime_list[j*i] = False
      j+=1

1

aw4lly 21 Nov. 2012 im 06:54

Answer 2

Zunächst die Antwort auf Ihre spezifische Frage. Sie verwerfen die Primzahlen, die kleiner als die Quadratwurzel von n sind. Die einfachste Lösung besteht darin, die Zeile num[i] = False am Ende Ihrer inneren Schleife in num[i] = (not x == i) zu ändern (ich denke, das funktioniert, ich habe es nicht getestet).

Zweitens ist Ihr Algorithmus eine Versuchsteilung, nicht das Sieb von Eratosthenes, und hat die Zeitkomplexität O (n ^ 2) anstelle von O (n log log n). Der Modulo-Operator verschenkt das Spiel. Das einfachste Sieb von Eratosthenes sieht so aus (Pseudocode, den Sie in Python übersetzen können):

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    output p
    for i from p+p to n step p
      sieve[i] := False

Es gibt Möglichkeiten, diesen Algorithmus zu verbessern. Wenn Sie an der Programmierung mit Primzahlen interessiert sind, empfehle ich diesen Aufsatz , der ein optimiertes Eratosthenes-Sieb enthält, in bescheidenem Umfang Implementierung in Python.

1

user448810 21 Nov. 2012 im 15:24

Answer 3

Wenn Sie durch num iterieren, ist x manchmal gleich i, sodass i % x gleich 0 ist und i als Nicht-Primzahl markiert wird.

Sie müssen if not x == i: irgendwo in Ihrer while-Schleife hinzufügen, z.

while x < limit:
        for i in num:
            if not x == i:
                if num[i] and i%x==0:
                    num[i] = False

1

Marius 21 Nov. 2012 im 05:36

Answer 4

Importzeit

Def primes_sieve1 ():

limitn = int(raw_input("Please enter an upper limit ")) +1
start = time.clock()
primes = {
    }

for i in range(2, limitn):
    primes[i] = True

for i in primes:
    factors = range(i,limitn, i)
    for f in factors[1:]:
        primes[f] = False

end = time.clock()
print "This took ",end-start," seconds"
return [i for i in primes if primes[i]==True]

Primes_sieve1 ()

Anstatt Division zu verwenden, nimmt dieser Code die Vielfachen aller Zahlen, die kleiner als die Wurzel des Grenzwerts sind, und ändert sie in false. Dies ist etwas schneller, da nicht jede Zahl durch eine andere Zahl geteilt wird.

Auch unter 1000 tritt die Situation auf, dass eine Primzahl von selbst moduliert wird, um 0 zu ergeben, und das Programm dies für falsch hält. Da der sqrt (1000) ungefähr 31 beträgt, sind Primzahlen unter 31 betroffen.

Zum Beispiel tritt in der 7. Schleife von "while x

0

Aaron 18 Feb. 2015 im 16:49

Meine Implementierung des Eratosthenes-Siebs ist fehlerhaft?

4 Antworten

Verwandte Fragen

Neue Fragen

python