Frage zu einfachem Algorithmus zu Primzahlen auf Wikipedia



  • Hey,
    ich habe hier auf Wikipedia einen Algorithmus zur Trialdivision gefunden, um Primzahlen zu finden: http://en.wikipedia.org/wiki/Trial_division#Method (Der Python Code)
    Was ich daran nicht verstehe sind 2 Dinge:

    • primes = prime_sieve(int(n**0.5) + 1)
    • if p*p > n: break

    Zum ersten Punkt: Sollte es nicht reichen, alle Primzahlen bis sqrt(n) zu bestimmen? Wieso also noch +1? Wenn ich mir das Extrembeispiel 49 nehme: sqrt(49) ist 7, wieso sollte ich noch auf 8 testen?

    Zum zweiten Punkt: Dadurch, dass wir im ersten Punkt alle Primzahlen herausgesucht haben, die <= sqrt(n) sind, ist dieses Abbruchkriterium dann nicht redundant?

    ├ťbersehe ich hier etwas, oder ist das einfach falsch?



  • *0.5+1 ist doch so ein Rundungsding ­čśĽ


  • Mod

    PrimZahl schrieb:

    Zum ersten Punkt: Sollte es nicht reichen, alle Primzahlen bis sqrt(n) zu bestimmen? Wieso also noch +1? Wenn ich mir das Extrembeispiel 49 nehme: sqrt(49) ist 7, wieso sollte ich noch auf 8 testen?

    Bist du dir sicher, dass die Flie├čkommawurzelberechnung wirklich immer exakt auf einen Ganzzahlwert kommt? Falls sqrt(49) nicht 7 sondern 6.999999999999998 sein sollte, dann rechnet das Programm ohne die +1 falsch.

    Zum zweiten Punkt: Dadurch, dass wir im ersten Punkt alle Primzahlen herausgesucht haben, die <= sqrt(n) sind, ist dieses Abbruchkriterium dann nicht redundant?

    Dann hast du den Algorithmus an sich nicht verstanden. Wenn die Zahl Beispielsweise 1024 ist, dann bekommen wir im ersten Schritt schon 10 Mal den Primfaktor 2, unser neues n ist 1 und wir k├Ânnen uns die restlichen 10 m├Âglichen Primfaktoren sparen.


  • Mod

    Der Grund, den SeppJ nennt, ist schon richtig. Wenn ich mich nicht irre, verlangt allerdings der ├╝bliche Flie├čkomma-Standard IEEE754, dass sqrt so exakt rechnen muss wie durch die Flie├čkommadarstellung m├Âglich, d.h. es muss das exakte Ergebnis genommen und nach dem aktuellen rounding mode gerundet werden.

    Integer-Quadratzahlen (bis zu einer gewissen Schranke) lassen sich in float oder double-Werten exakt darstellen, ohne Rundungsfehler. sqrt muss dann aber auch die korrekte Wurzel als Ergebnis liefern, ohne jeden Rundungsfehler, denn das Ergebnis l├Ąsst sich exakt darstellen.


  • Mod

    Stimmt. Und sqrt sollte eigentlich auch mit dieser Begr├╝ndung korrekt rechnen, ebenso pow. Zumindest, wenn Python sich garantiert an die ├╝blichen Flie├čkommastandards h├Ąlt. Tut es das? Wer hat Lust, das auf Wikipedia zu erkl├Ąren?


Log in to reply