026
26.01.2007, 23:48 Uhr
tobias
hmm....
|
und das hilft vllt. auch noch..
das ist das sieb des erathors oder wie der heinz da heißen mag.
Dieses funktioniert nach folgendem Prinzip:
Schreibt man eine Liste aller natürlichen Zahlen auf, die man überprüfen will, dann sieht das nachher z.B. so aus:
Hab hier ein wenig gestrichen.... hier waren die zahlen 1 bis 100 aufgelistet.. also:
1,2,3,4,5,6.................................................,99,100
a) Nun streicht man als erstes die 1 weg, da es sich bei 1 um keine Primzahl handelt.
b) Es folgt die 2. 2 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 2 als Primzahl.
c) Wir streichen nun alle durch 2 teilbaren Zahlen, weil diese nicht Primzahlen sein können. (Sie hätten jeweils die Teiler 1,2 und sich selbst)
d) Die 3 ist nun die nächste ungestrichene Zahl! Wir markieren 3 als Primzahl.
e) Wir streichen nun alle durch 3 teilbaren Zahlen, weil diese ebenfalls keine Primzahlen mehr sein können.
f) Nun wiederholen wir Schritt d) und e) bis alle Zahlen entweder als Primzahlen markiert, bzw. als Nichtprimzahlen durchgestrichen sind. Achtung: Diese Schritte müssen nur bis zur Zahl durchgeführt werden, die größer oder gleich der Wurzel des zu überprüfenden Bereich ist. z.B. 10 bei 100, 32 bei 1000, da 10 * 10 = 100 bzw. 32 * 32 = 1024 > 1000
Man erhält in dem oberen Beispiel nun eine Liste von Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
--
Danke |
