Hat vielleciht jemand einen Vorschlag für einene verfahren, Primzahlen zu ermitteln?
Jede Zahl Modulo jeder Zahl unter ihr ist doch ziemlch langsam, auch wenn man vorher ersat mal mit modulo 2 und 5 vorsortiert.
Kennt jemand einen Algorythmus oderein verfahren, Primzahlenschnellerzu finden?
Grüße, Ryo
mr.escape Plazebo „Sieb des Eratosthenes ist ziemlich fix, aber nicht die beste Methode glaube ich....“
>2 ist keine Primzahl ... Nicht? Dachte immer, zwei wäre die kleinste primzahl. Tja, so kann man sich irren.
>Daher streichst du alles Vielfache von 2 (4, 6, 8, 10 etc.) indem du meinetwegen in die Stelle des Arrays auf True oder False setzt.
Dann gehst du wieder unüberprüft mit 3, also erhöhst immer um einen.
3 ist auch keine Primzahl und du setzt wieder in jede 6., 9. 12. Stelle usw. das Array auf True oder False (das kannst du nach Belieben machen).
Nach der zwei (sofern man das array nicht sogar nur für ungerade zahlen anlegt, das spart auch speicherplatz) überprüft man nur noch die (ungeradzahligen) vielfachen von ungeraden, denn die sind mit der zwei ja schon aus dem rennen, d.h. man erhöht immer um zwei, ausgehend von 3 (3,5,7,9, etc.).Zusätzlich lässt man alle weg, die schon in der tabelle gekillt sind (z.b. 9, 15, 21, etc.), dann geht es etwas schneller.
mr.escape
