Primzahlen Berechnung + weitere Verarbeitung
-
SeppJ schrieb:
Noch besser: Man kennt ja schon die kleineren Primzahlen. Dies sind die einzigen Zahlen die man testen muss.
Wenn man sie kennt.
Das ersetzt aber nur meinen letzten Vorschlag mit den ungeraden Zahlen.
-
Kautabak schrieb:
SeppJ schrieb:
Noch besser: Man kennt ja schon die kleineren Primzahlen. Dies sind die einzigen Zahlen die man testen muss.
Wenn man sie kennt.
Naja, es geht hier ja darum, gerade alle Zahlen bis zu einem bestimmten Bereich zu finden, daher liegt es nahe, dass man die kleinen Zahlen kennt.
Wenn man die kleineren Zahlen nicht kennt, wäre der nächste Schritt nach nur ungeraden Zahlen zu testen, auch die Zahlen die durch 3 teilbar sind nicht zu testen. Also nur noch 2, 3 und Zahlen der Form (6k +- 1). Und das treibt man dann noch weiter und nennt es Sieb des Eratosthenes. Und somit hätte man natürlich wieder eine recht effiziente Methode alle Primzahlen bis zu einem bestimmten Wert zu finden.
Und natürlich gibt es da noch die besseren Tests der Zahlentheorie für wirklich große Zahlen, aber dies führt hier zu weit. Bei einer Übungsaufgabe an einer Hochschule würde ich aber schon erwarten, dass Studenten selbstständig auf etwas ähnliches wie die Siebmethode kommen. Hier wurde ja noch nicht einmal erkannt, dass man nur bis Wurzel(p) testen braucht.
Und es ist auch hochgradig ungünstig wie hier bei dem Test den Zahlenraum von oben her durchzulaufen. Jede zweite Zahl würde man nämlich schon im ersten Durchlauf erschlagen, wenn man bei 2 beginnen würde, was ebenfalls viel Zeit sparen würde.
-
SeppJ schrieb:
Hier wurde ja noch nicht einmal erkannt, dass man nur bis Wurzel(p) testen braucht.
Viel übler finde ich das mit den geraden Zahlen. :p
Darum auch nur meine zwei Hinweise. Die lassen sich recht einfach in ihre bestehenden Codes einbauen.
