Debugging eines Python Prime Number Programms

Question

Ich schrieb den Code für einen Python-Primzahlengenerator, um die ersten 100 Primzahlen zu erzeugen. Aber irgendwie bekomme ich Nicht-Primzahlen wie 22, 25 usw. in meiner Ausgabe. Ich habe es wieder stundenlang überprüft und kann immer noch nicht herausfinden, wo ich falsch gelaufen bin ... Bitte helfen Sie mir!

Hier ist mein Code:

from math import sqrt 

y=[2] 
x=3 

while len(y)!=100: 
    for i in range (2,int(round(sqrt(x)+1))): 
    if x%i==0: 
     x=x+1 

    else: 
     y.append(x) 
     x=x+1 
     break 

print(y) 

Answer 1

der Inhalt Ihrer sonst außerhalb der for-Schleife sein sollte. Hier fügen Sie x an Ihr Array an, sobald es nicht geteilt wurde durch "mindestens eines der i" anstelle von "nicht durch jedes i geteilt werden". Auch diese Algorithmen sind sehr ineffizient. Für einen schnellen einen Versuch: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

from math import sqrt 

y=[2] 
x=3 

while len(y)!=100: 
    prime = True 
    for i in [ i for i in y if i < sqrt(x) + 1 ]: 
     if x%i==0: 
      prime = False 
      break 

    if prime: 
     y.append(x) 

    x=x+1 


print(y) 

Bitte beachte, dass ich bereits Ihren Algorithmus optimiert, indem nur dividiert durch vorher Primzahlen gefunden.

Answer 2

Ihr Test für eine Nummer, die prime ist, ist falsch. Sie überprüfen, ob eine Zahl durch i von 2 bis sqrt(x) teilbar ist, was korrekt ist, aber sobald Sie eine Zahl treffen, die kein Faktor ist, nehmen Sie an, dass die Zahl prim ist, was nicht korrekt ist. Sie haben alle Zahlen zu überprüfen und, wenn keine Rolle spielt, dann können Sie davon ausgehen, dass Ihre Zahl prim ist:

from math import sqrt 

y=[2] 
x=3 

while len(y)!=100: 
    isPrime=True 
    for i in range (2,int(round(sqrt(x)+1))): 
     if x%i==0: 
      x=x+1 
      isPrime=False 
      break    # See Mr Nun's answer 
    if(isPrime): 
     y.append(x) 
     x=x+1 

print(y) 

Wie wurde darauf hingewiesen, ist dies nicht eine sehr effiziente Lösung. Sehen Sie sich den Link in der Antwort von @ user2346536 an.

Answer 3

Wie Benutzer2346536 sagte, Ihr sonst sollte nicht innerhalb der Schleife sein. Sie werden immer nur an dem Element sucht i = 2

Wie es zu tun:

from math import sqrt, ceil 
prime_list = [2] 
x = 2 
while prime_list != 100: 
    x += 1 
    is_prime = True 
    for element in range(2,int(ceil(sqrt(x)))): 
     # if x is divided, then we go to next iteration 
     if x%element == 0: 
      is_prime = False 
      break 
    if is_prime: 
     y.append(x) 

Answer 4

ich hätte es so gemacht; ein bisschen mehr Pythonic:

y = [2] 
x = 3 
while len(y) < 100: 
    if all(x % i != 0 for i in range(2, int(round(sqrt(x) + 1)))): 
     y.append(x) 
    x = x + 1 

print(y) 

Die all() Funktion ist sehr nützlich.

Dies ist ähnlicher zu dem, was Sie getan haben; Bitte beachten Sie die break Aussage und was es tut:

from math import sqrt 

y=[2] 
x=3 

while len(y) != 100: 
    is_prime = True 
    for i in range (2, int(round(sqrt(x) + 1))): 
     if x % i == 0: 
      x += 1 
      is_prime = False 
      break # this means that x is not prime and we can move on, note that break breaks only the for loop 
    if is_prime: 
     y.append(x) 
     x += 1 

print(y) 

Answer 5

Die anderen Antworten sind richtig, aber keiner von ihnen zeigen, dass Sie tatsächlich eine else Klausel über die for Schleife verwenden können. Lesen Sie mehr dazu here. Sie brauchen also die if is_prime: Anweisung nicht. Der resultierende Code könnte in etwa so aussehen.

from math import sqrt 

y = [2] 
x = 3 

while len(y) != 100: 
    for i in range (2, int(round(sqrt(x) + 1))): 
     if x % i == 0: 
      x = x + 1 
      break 

    else: 
     y.append(x) 
     x = x + 1 
print(y) 

Tipp: x+=1 konnte x=x+1

Darüber, wie @ user2346536 ersetzen, können Sie tatsächlich einen viel effizienteren Algorithmus verwenden, um die Primzahlen für die Berechnung, was wichtig ist, wenn Sie über eine große Anzahl sind Looping.