Primzahlen – Sieb des Eratosthenes

Quelle: ZPG IMP

Primzahlen sind bereits seit der Antike bekannt. Schon die „alten Griechen“, z.B. Euklid und Eratosthenes, widmeten sich den Primzahlen und entdeckten zahlreiche spannende mathematische Eigenschaften rund um Primzahlen. Aber auch in neueren Jahren beschäftigten sich viele Mathematiker mit Primzahlen, darunter so berühmte Namen wie Euler, Fermat, Goldbach oder auch Gauss. Im Feld der Kryptologie, also der Wissenschaft vom Ver- und Entschlüsseln von Botschaften durch (mathematische) Regeln, bekamen Primzahlen im Verlauf der letzten knapp 100 Jahre eine immer wichtigere Bedeutung. Es begann eine regelrechte Jagd nach großen Primzahlen.

Doch beginnen wir von Anfang an. Zunächst wiederholen wir nochmals, was eine Primzahl überhaupt ist:

Deine Aufträge:

1. Begründe, dass die Zahl 1 keine Primzahl ist.

2. Um Primzahlen zu finden, kann man das folgende Verfahren durchführen, das sogenannte Sieb des Eratosthenes. Zuerst wird die Zahl 1 gestrichen. Die Zahl 2 wird umkreist und dann alle Vielfachen von ihr gestrichen. Dann wird die nach der 2 nächste nicht gestrichene Zahl, die 3, umkreist und alle Vielfachen von ihr gestrichen. Jetzt wird die nach der 3 nächste freie Zahl umkreist (die 5) und ihre Vielfachen gestrichen, usw. Den Anfang siehst du im folgenden Beispiel. Fertige eine Tabelle der Zahlen bis 100 an und führe das Schema vollständig durch – umkreist bleiben nur die Primzahlen übrig.

   

3. „Wenn man eine beliebige natürliche Zahl k wählt und dann 2^k - 1 berechnet, so erhält man stets eine Primzahl, z.B. 2² - 1 = 3“. Ist diese Aussage richtig? Begründe.

   Übrigens: Man nennt Zahlen der Art 2^k - 1 Mersenne-Zahlen. Bei der „Jagd“ nach hohen Primzahlen fokussieren sich Mathematiker heute auf diese Zahlen, darunter die Zahl 2^77232917 - 1, die zu Beginn des Jahres 2018 höchste bekannte Primzahl. Sie wurde durch verteiltes Rechnen bestimmt. Mehr dazu findest du im Internet, wenn du nach Mersenne-Zahlen suchst.

4. a.) Berechne für k = 1 bis 5 fünf verschiedenen Zahlen auf die folgende Art: Multipliziere die ersten k Primzahlen miteinander und addiere 1. Beispiel: Für k = 2 ist dies 2 * 3 + 1 = 7.

   b.) Betrachte die Ergebnisse aus a.). Was fällt dir an der Einerstelle auf? Prüfe an ein paar Beispielen, ob deine Idee auch für k > 5 gilt. Versuche die Beobachtung zu erklären.

   c.)* Teile die fünf Zahlen aus a.) nacheinander durch jede einzelne Primzahl, die zu ihrer Berechnung verwendet wurde. Verwende „Teilen mit Rest“. Was fällt dir auf? Begründe.

5. a.)* Programmiere das Sieb des Erathostenes wahlweise für eine fest vorgegebene Zahl n (z.B. 1000), oder bis zu einer Zahl, die das Programm vom Nutzer zunächst abfragt.

   b.)* Erkläre das Prinzip, nach dem das Sieb des Eratosthenes funktioniert.

   c.)** Wiederhole Aufgabe 4 mit weiteren Werten für k. Stelle dann eine begründete Vermutung auf: Kann es eine größte Primzahl geben? Prüfe mithilfe von Primzahltabellen, welche Zahlen davon Primzahlen sind. Die Nicht-Primzahlen darunter lassen sich in ein Produkt aus Primzahlen zerlegen ¹. Vergleiche diese Primzahlen mit denen zur Erzeugung verwendeten Primzahlen aus Aufgabe 4. Stelle dann eine begründete Vermutung auf: Kann es eine größte Primzahl geben?

AB Primzahlen – Sieb des Eratosthenes:

Zu Aufgabe 4a.) Alle Primzahlen zwischen 0 und 2500:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477

Primzahlen – Sieb des Eratosthenes: Herunterladen [odt][362 KB]

Primzahlen – Sieb des Eratosthenes: Herunterladen [pdf][160 KB]

Weiter zu Teilbarkeit und Teilbarkeitsregeln