Sieb des Erathostenes: der Algorithmus zum Finden der Primzahlen in einer Liste. Löschen Vielfachen der kleineren Primzahlen

Der griechische Mathematiker ERATOSTENE (275 - 194 v. Chr.) Hat eine neue und einfache Methode angewendet, um zu bestimmen, ob die Zahlen in einer Liste Primzahlen sind oder nicht. Ausgehend von den bekannten kleinen Primzahlen 2, 3, 5, 7, 11, 13, 17, 21 usw. ist klar, dass alle ihre Vielfachen keine Primzahlen, sondern zusammengesetzte Zahlen sind. Er hat eine Liste von natürlichen Zahlen in aufsteigender Reihenfolge angeordnet und dann alle Vielfachen der ersten Primzahlen entfernt, um den Rest der größeren Primzahlen in dieser Liste zu identifizieren. Wir werden diese Methode unten auf einer Liste von Zahlen von 2 bis 100 veranschaulichen:

  • Nummer 2 ist Primzahl, also entfernen wir aus dieser Zeichenkette alle Vielfachen von 2: 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 zu 2 × 50 = 100. 2 × 51 = 102, ist größer als 100, also hören wir auf.
  • Vielfache von 2 aus der Liste entfernen: 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 (zwei-mal-zwei-Nummern).
  • 3 ist die nächste Primzahl, also werden wir alle Vielfachen von 3: 3 × 2 = 6 (die bereits aus der Liste entfernt wurden, ein Vielfaches von 2) aus der Liste entfernen; 3 × 3 = 9; 3 × 4 = 12 (das bereits von der Liste entfernt wurde, ein Vielfaches von 2 ist); 3 × 5 = 15; 3 × 6 = 18 (das bereits von der Liste entfernt wurde, ein Vielfaches von 2 ist); ... und so weiter bis: 3 × 33 = 99. 3 × 34 = 102, ist größer als 100, also hören wir auf.
  • Vielfache von 3 aus der Liste entfernen: 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 (drei zu drei Zahlen). Wenn wir nicht die Vielfachen von 2 betrachten, die bereits aus der Liste entfernt wurden, haben wir noch: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, dh. Zahlen, die als Faktoren nur Primzahlen größer oder gleich 3: 3 × 3 = 9 haben; 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 werden auch mit der folgenden Primzahl fortfahren, 5: 5 × 2 = 10 (die bereits aus der Liste entfernt wurde, was ein Vielfaches von 2 ist); 5 × 3 = 15 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 3); 5 × 4 = 20 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 2); 5 × 5 = 25; 5 × 6 = 30 (welches bereits aus der Liste entfernt wurde, wobei es ein Vielfaches von 2 und 3 ist); 5 × 7 = 35; ... und so weiter bis zu: 5 × 20 = 100 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 2). 5 × 21 = 105, ist größer als 100, also hören wir auf.
  • Vielfache von 5 aus der Liste entfernen: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (Fünf-mal-fünf-Nummern). Wenn wir nicht auf die Vielfachen von 2 und 3 schauen, die bereits aus der Liste entfernt wurden, müssen wir noch entfernen: 25, 35, 55, 65, 85, 95, dh. genau die Zahlen, die als Faktoren nur Primzahlen größer oder gleich 5: 5 × 5 = 25 haben; 5 × 7 = 35; 5 × 11 = 55; 5 × 13 = 65; 5 × 17 = 85; 5 × 19 = 95.
  • Dann machen wir dasselbe mit der folgenden Primzahl, 7: 7 × 2 = 14 (die bereits aus der Liste entfernt wurde und ein Vielfaches von 2 ist); 7 × 3 = 21 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 3); 7 × 4 = 28 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 2); 7 × 5 = 35 (welches bereits aus der Liste entfernt wurde, ist ein Vielfaches von 5); 7 × 6 = 42 (welches bereits aus der Liste entfernt wurde und ein Vielfaches von 2 und 3 ist); ... 7 × 7 = 49; ... und so weiter bis zu: 7 × 14 = 98 (das bereits aus der Liste entfernt wurde und ein Vielfaches von 2 ist). 7 × 15 = 105, ist größer als 100, also hören wir auf.
  • Vielfache von 7 aus der Liste entfernen: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (Sieben-für-sieben-Zahlen). Wenn wir nicht auf die Vielfachen von 2, 3 und 5 schauen, die bereits aus der Liste entfernt wurden, müssen wir noch entfernen: 49, 77, 91, dh. genau die Zahlen, die als Divisoren nur Primzahlen größer oder gleich 7: 7 × 7 = 49 haben; 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 oben gesehen haben, sollten wir nur Zahlen aus der Liste entfernen, die als Divisoren nur Primzahlen größer oder gleich 11 haben. Aber schon 11 × 11 = 121 ist größer als 100, das bedeutet, dass alle Zahlen übrig sind Die Liste nach dem oben beschriebenen Prozess sind bereits Primzahlen.
  • Nachdem wir alle Vielfachen der Primzahlen 2, 3, 5 und 7 aus der Liste entfernt haben, haben wir immer noch 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, das heißt, die Liste der Primzahlen von 2 bis 100.

Was ist eine Primzahl?

Was ist eine zusammengesetzte Nummer?

Primzahlen bis 1.000

Primzahlen bis 10.000

Erastotene Sieb

Euclid Algorithmus

Reduzieren gewöhnlichen Mathematik Fraktionen Bedingungen zu senken (vereinfacht): Schritte und Beispielen