Zitat von
moritz:
Zitat von
Binärbaum:
Zitat von
moritz:
Kurze Theorie zu den Primzahlen:
Primzahlen unterteilen sich in zwei Gruppen: Solche, die sich als 4n+1, und solche, die sich als 4n-1 darstellen lassen. Das ist schonmal eine Eigenschaft, mit der man die Anzahl der zu prüfenden Zahlen schonmal drastisch reduzieren kann.
Kommt das nicht auf das selbe raus wie
2n+1?
Das heißt dann ja, dass alle Primzahlen ungerade sind (bis auf die 2), und das ist ja auch nichts Neues.
MfG
Binärbaum
Nein. Durch 4n+1 btzw 4n-1 erreichst du weniger Zahlen und dadurch eine höhere Geschwindigkeit.
Das stimmt nicht. Mit 4n+1 und 4n-1 erreicht man ja immer zwei von vier Zahlen, mit 2n+1 eine von zwei Zahlen. Das Verhältnis ist gleich (2/4=1/2). Bei beiden Varianten wird also die Hälfte aller Zahlen betrachtet. Damit ist es egal, welche Variante man nimmt.
(2n+1 ist sogar einfacher, weil man nur eine Formel hat statt zwei.)
MfG
Binärbaum