Primzahltests
Sieb des Eratosthenes*
Einfache Prinzipdarstellung Komplexe Darstellung
Einfache Prinzipdarstellung
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:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
|
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 |
|
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
|
61 |
62 |
63 |
64 |
65 |
66 |
67 |
68 |
69 |
70 |
|
71 |
72 |
73 |
74 |
75 |
76 |
77 |
78 |
79 |
80 |
|
81 |
82 |
83 |
84 |
85 |
86 |
87 |
88 |
89 |
90 |
|
91 |
92 |
93 |
94 |
95 |
96 |
97 |
98 |
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.
Komplexe Darstellung
Schreibt man eine Liste aller natürlichen Zahlen auf, die man überprüfen will. Hier im Beispiel bis 660.
Achtung: Diese Schritte müssen nur bis zur Zahl durchgeführt werden, die größer oder gleich der Wurzel des zu überprüfenden Bereiches ist. Z.B. 10 bei 100, 32 bei 1000, da 10 * 10 = 100 bzw. 32 * 32 = 1024 > 1000. Hier bei 660 bis 26.
Nun streicht man als erstes die 1 weg, da es sich bei 1 um keine Primzahl handelt.
Es folgt die 2. Die Zahl 2 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 2 als Primzahl und streichen
nun alle durch 2 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 2. Sie liegen alle auf Geraden.
Es folgt die 3. Die Zahl 3 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 3 als Primzahl und streichen nun alle durch 3 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 3. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 5. Die Zahl 5 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 5 als Primzahl und streichen nun alle durch 5 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 5. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 7. Die Zahl 7 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 7 als Primzahl und streichen nun alle durch 7 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 7. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 11. Die Zahl 11 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 11 als Primzahl und streichen nun alle durch 11 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 11. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 13. Die Zahl 13 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 13 als Primzahl und streichen nun alle durch 13 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 13. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 17. Die Zahl 17 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 17 als Primzahl und streichen nun alle durch 17 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 17. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 19. Die Zahl 19 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 19 als Primzahl und streichen nun alle durch 19 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 19. Sie liegen alle auf Geraden.
Es werden nur ungestrichene Zahlen beachtet.
Es folgt die 23. Die Zahl 23 wurde bis jetzt nicht weggestrichen und ist deshalb Primzahl. Wir markieren 23 als Primzahl und streichen nun alle durch 23 teilbaren Zahlen, weil diese nicht Primzahlen sein können. Sie hätten jeweils den Teiler 23. Sie liegen alle auf Geraden.
Die Zahlen 24, 25 und 26 sind schon gestrichen. Jetzt ist das Ziel erreicht. Alle noch nicht gestrichenen Zahlen sind Primzahlen (siehe oben).
Wir markieren die restlichen Zahlen als Primzahlen.
* griechischer Gelehrter und Dichter aus Kyrene, * um 275 v. Chr., † um 195 v. Chr.; Leiter der Bibliothek von
Alexandria, bezeichnete sich als Erster als Philologe; er berechnete annähernd richtig den Umfang der Erdkugel aus den Sonnenhöhen an 2 Punkten des gleichen Meridians und entwarf
eine Erdkarte; erzählende Gedichte: "Hermes", "Erigone". (Quelle: www.wissen.de)