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?


Anmelden zum Antworten