Die Primzahlen und das Sieb des Eratosthenes: Der Algorithmus dient dazu, die Primzahlen in einer Liste zu identifizieren - Tipp: Beginnen Sie damit, die Vielfachen der kleineren Primzahlen zu eliminieren

Der griechische Mathematiker ERATOSTENE (275 - 194 v. Chr.) verwendete eine neue und einfache Methode, um festzustellen, ob die Zahlen in einer Liste Primzahlen sind oder nicht.
Er begann mit den bekannten kleinen Primzahlen 2, 3, 5, 7, 11, 13, 17, 23 usw. Es ist klar, dass alle ihre Vielfachen keine Primzahlen, sondern zusammengesetzte Zahlen sind.
Er ordnete eine Liste natürlicher Zahlen in aufsteigender Reihenfolge. Dann identifizierte und entfernte er alle größeren zusammengesetzten Zahlen in dieser Liste, da sie Vielfache der ersten Primzahlen waren, und grenzte somit die größeren Primzahlen in dieser Liste ab.
Wir veranschaulichen diese Methode unten mit einer Liste von Zahlen, die in aufsteigender Reihenfolge von 2 bis 100 sortiert sind:

Die Zahl 2 ist eine Primzahl, also identifizieren wir zuerst alle Vielfachen von 2 in der Liste:
2 × 2 = 4
2 × 3 = 6
2 × 4 = 8
2 × 5 = 10
2 × 6 = 12
2 × 7 = 14
2 × 8 = 16
2 × 9 = 18
2 × 10 = 20
... und so weiter, bis zur Zahl: 2 × 50 = 100.
Die Zahl 2 × 51 = 102, ist größer als 100, also können wir aufhören.
Entfernen Sie die Vielfachen der Zahl 2 aus der Liste: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.

Die Zahl 3 ist eine Primzahl, also identifizieren wir zuerst alle Vielfachen von 3 in der Liste:
3 × 2 = 6 (Diese Zahl wurde bereits aus der Liste entfernt, sie ist ein Vielfaches von 2);
3 × 3 = 9
3 × 4 = 12 (Diese Zahl wurde bereits aus der Liste entfernt, sie ist ein Vielfaches von 2);
3 × 5 = 15
3 × 6 = 18 (Diese Zahl wurde bereits aus der Liste entfernt, sie ist ein Vielfaches von 2);
... und so weiter, bis zur Zahl: 3 × 33 = 99.
Die Zahl 3 × 34 = 102, ist größer als 100, also können wir aufhören.
Entfernen Sie die Vielfachen der Zahl 3 aus der Liste: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
Wenn wir bereits alle Vielfachen der Zahl 2 aus der Liste entfernt haben, haben wir noch: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Diese Zahlen werden unten als Vielfache der Zahl 3 geschrieben:
3 × 3 = 9
3 × 5 = 15
3 × 7 = 21
3 × 9 = 3 × 3 × 3 = 27
3 × 11 = 33
3 × 13 = 39
3 × 15 = 3 × 3 × 5 = 45
3 × 17 = 51
3 × 19 = 57
3 × 21 = 3 × 3 × 7 = 63
3 × 23 = 69
3 × 25 = 3 × 5 × 5 = 75
3 × 27 = 3 × 3 × 3 × 3 = 81
3 × 29 = 87
3 × 31 = 93
3 × 33 = 3 × 3 × 11 = 99.

Wir fahren dann mit der folgenden Primzahl 5 fort:
5 × 2 = 10 (Diese Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2);
5 × 3 = 15 (Diese Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 3);
5 × 4 = 20 (Diese Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2);
5 × 5 = 25
5 × 6 = 30 (diese Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2 und 3);
5 × 7 = 35
... und so weiter, bis zur Zahl: 5 × 20 = 100 (Diese Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2).
Die Zahl 5 × 21 = 105, ist größer als 100, also hören wir auf.
Entfernen Sie die Vielfachen von 5 aus der Liste: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Wenn wir uns nicht die Vielfachen von 2 und 3 ansehen, die bereits aus der Liste entfernt wurden, müssen wir noch entfernen: 25, 35, 55, 65, 85, 95, dh. genau die Zahlen, die in ihrer Primfaktorzerlegung nur Primfaktoren größer oder gleich 5 haben:
5 × 5 = 25
5 × 7 = 35
5 × 11 = 55
5 × 13 = 65
5 × 17 = 85
5 × 19 = 95.

Dann wiederholen wir den Vorgang mit der nächsten Primzahl 7:
7 × 2 = 14 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2);
7 × 3 = 21 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 3);
7 × 4 = 28 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2);
7 × 5 = 35 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 5);
7 × 6 = 42 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2 und 3);
7 × 7 = 49
... und so weiter, bis zur Zahl: 7 × 14 = 98 (die Zahl wurde bereits aus der Liste entfernt - sie ist ein Vielfaches von 2).
7 × 15 = 105, ist größer als 100, also hören wir auf.
Entfernen Sie die Vielfachen von 7 aus der Liste: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Wenn wir uns nicht die Vielfachen von 2, 3 und 5 ansehen, die bereits aus der Liste entfernt wurden, müssen wir noch entfernen: 49, 77, 91. Das sind genau die Zahlen, die Primfaktoren haben, die in ihrer Primfaktorzerlegung größer oder gleich 7 sind:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

Die nächste Primzahl in der Liste ist 11 und wir sollten die Vielfachen von 11 aus der Liste entfernen.
Wie wir jedoch bei den obigen Schritten gesehen haben, sollten wir nur versuchen, Zahlen aus der Liste zu entfernen, deren Primfaktoren größer oder gleich 11 sind.
Aber schon 11 × 11 = 121, was größer als 100 ist. Das bedeutet, dass alle Zahlen, die nach Durchführung aller obigen Schritte in der Liste übrig bleiben, bereits Primzahlen sind.

Die Liste der Primzahlen besteht aus den nicht entfernten Zahlen.
Nachdem wir alle Vielfachen der Primzahlen 2, 3, 5 und 7 entfernt haben, haben wir immer noch diese Zahlen in der Liste: 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, also die Liste der Primzahlen von 2 bis 100.

de.numere-prime.ro