Die Primzahlsuche history menue Letztmalig dran rumgefummelt: 31.08.15 16:29:53

Die Primzahlen sind Klassiker der Mathematik und auch für findige Algorithmen in der Informatik eine erste Adresse :-)
International laufen sich Computer heiß, werden neue, und vor allem effizientere Algorithmen gesucht, welche die Forschung nach weiteren, vor allem sehr großen Primzahlen beschleunigen sollen und hoffen vor allem Kryptologen, dass dies nicht so schnell gelingen möge. Sehr große Primzahlen sind nämlich heutzutage die Basis aller als sicher geltenden Chiffrierungsalgorithmen.
1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Informationen
7. Linkliste zum Thema
8. Verwandte Themen

Probleme & Problemlösungsverfahren

Logo für die Primzahlsuche

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Basiswissen der Informatik

Wissen für Fortgeschrittene der Informatik

Quellen:

LOG IN - Heft 146/147 (2007) Seite 47 ff.


1. Problembeschreibung history menue scroll up

Es gibt keine Periodizität und kein Muster in den Primzahlen. Soviel ist sicher, der Anteil der Primzahlen unter den ersten N natürlichen Zahlen sinkt mit steigendem N. Unter den ersten 100 natürlichen Zahlen gibt es 25 Primzahlen (25%), unter den ersten 1000 sind es 168 (16.8%), unter den ersten 100000 sind es 9592 (9.6%) und unter den ersten 10 Millionen sind es 664759 Primzahlen (6.65%).
Zahlen, die nicht geteilt werden können

Da waren irgendwann in früheren Zeiten Bauern mit ihrem Vieh. Sie mussten ihre Schafe zählen, um herauszufinden, ob keines verlorengegangen ist. So kamen sie auf die ganzen Zahlen. Wer sich eine Frau nahm, erhielt weitere Tiere aus ihrer Mitgift, und er musste lernen, zwei Zahlen zusammenzuzählen. Heiratete die Tochter, bekam sie Rinder und Schafe mit in die neue Ehe - der Vater musste das Subtrahieren lernen. Als er alt wurde und sich Gedanken machte, wie er das Vieh gerecht an seine Kinder vererben könne, lernte er, Zahlen zu teilen. Ein Bauer mit zwölf Rindern merkte, dass ihm dies nur gelänge, wenn er zwei, drei, vier oder sechs Kinder hätte, während er dreizehn Rinder niemals gerecht verteilen könnte, es sei denn, er hätte nur eines oder dreizehn Kinder. Bei solchen Gedankengängen lernte der Mensch den Umgang mit ganzen Zahlen, und er lernte, dass sie nicht nur verschieden groß sind, sondern auch ganz verschiedene Charaktereigenschaften besitzen.
Bald stellte sich heraus, dass zwischen ganzen Zahlen die überraschendsten und kompliziertesten Beziehungen bestehen, und so entwickelte sich die Wissenschaft der Zahlentheorie. Sie befasst sich mit den Gesetzmäßigkeiten der ganzen Zahlen. Eine unübersehbare Menge von Büchern und Zeitschriftenartikeln zeigt, wie bunt und reichhaltig die Welt der ganzen Zahlen ist. Es ist nicht zu erwarten, dass ihre Erforschung sich jemals einem Ende nähert.
Ein anderes Beispiel, bei dem sich aus einigen wenigen Anfangsregeln ein riesiges Wissensgebiet entwickelt hat, ist das Schachspiel. Es gibt nur eine kleine Zahl von Vorschriften, wie eine Figur ziehen und eine andere schlagen darf. Aus diesen einfachen Regeln ergeben sich aber Strategien, die gleichfalls ganze Bücher füllen. Klassische Schachpartien großer Meister werden immer wieder in der Fachliteratur abgedruckt. Sie sind regelrechte Kunstwerke, und einige tragen auch den entsprechenden Namen, wie etwa «Die Unsterbliche», die der Breslauer Gymnasialprofessor für Mathematik Adolf Anderssen um die Mitte des 19. Jahrhunderts gewonnen hat. Doch auch dieses Meisterwerk war nur eine Folge von Anwendungen primitiver Regeln wie «Ein Bauer zieht gerade und schlägt schräg».
Während es im Schachspiel keine allgemeine Theorie gibt, wird das Spiel mit ganzen Zahlen von festen Lehrsätzen beherrscht. Wir haben bereits das Rechnen mit Resten kennen gelernt. Es stellt einen Teilbereich der Zahlentheorie dar. Man kann Zahlen zusammenzählen, man kann sie multiplizieren. Im Bereich ihrer Reste addieren oder multiplizieren sich dann ihre Reste. Das ist schon ein Satz der Zahlentheorie, wenn auch ein sehr einfacher. Ich will im folgenden auf ein anderes ihrer Teilgebiete eingehen, auf die Lehre von den Primzahlen. Sie spielen in der Verschlüsselung eine wichtige Rolle.
Zwei ganze Zahlen kann ich miteinander multiplizieren und erhalte wieder eine ganze Zahl, aus 10 mal 13 wird 130. Diese Zahl kann ich also durch 10 teilen, die Division geht auf. Auch bei der Division durch 2 oder 5 oder durch die 13 bleibt kein Rest. Die 130 ist eine zusammengesetzte Zahl, und auch die 10 ist zusammengesetzt, aus der 2 und der 5. Nicht aber die 13, sie hat keinen Teiler, sie ist eine Primzahl. Selbstverständlich ist die 13 durch 1 und sich selber teilbar, aber diese beiden primitiven Fälle wollen wir nicht betrachten. Die 2 ist eine Primzahl und auch die 3. Die 4 dagegen besitzt Teiler, die 5 wieder nicht. Wir haben also bereits die ersten Primzahlen: 2, 3, 5. Mit Ausnahme der 2 sind alle Primzahlen ungerade. Natürlich, sonst hätten sie ja die 2 als Teiler. Abbildung unten zeigt die Primzahlen bis 1013. Geht die Reihe, die ich bei 1013 abgebrochen habe, beliebig weiter? Gibt es also unendlich viele Primzahlen, oder gibt es eine größte und letzte und sind danach alle weiteren Zahlen durch kleinere teilbar? Diese Frage hat schon der griechische Mathematiker Euklid etwa dreihundert Jahre vor Christus beantwortet: Die Folge der Primzahlen hat kein Ende. Wir wissen also, dass unsere Primzahlentabelle noch beliebig weit fortgesetzt werden kann.

Warum es unendlich viele Primzahlen gibt

Nehmen wir an, es gäbe eine größte Primzahl, und nennen wir sie G. Dann multiplizieren wir alle Primzahlen, die kleiner sind, miteinander und mit G und zählen 1 dazu. Das Ergebnis nennen wir Y. Diese Zahl ist sicher größer als G, denn G wurde ja mit ganzen Zahlen multipliziert, und außerdem wurde noch die 1 addiert. Sie ist durch keine Primzahl kleiner als G und auch nicht durch G selbst teilbar, denn alle kleineren Primzahlen, einschließlich G, geben bei der Division den Rest 1. Damit ist bewiesen, dass Y entweder selbst eine Primzahl ist oder durch eine Primzahl größer als G teilbar sein muss. In beiden Fällen muss es eine Primzahl größer als G geben. Warum also gibt es unendlich viele Primzahlen? Weil man zu jeder eine größere finden kann

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 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

... die Primzahlen bis zu 1013

Wie können wir nun Primzahlen finden, die jenseits unserer Tabelle liegen? Ein einfaches Rezept dafür hat wiederum ein Grieche etwa zweieinhalb Jahrhunderte vor Christus gefunden. Eratosthenes von Kyrene. Er war der Leiter der berühmten Bibliothek von Alexandria und der erste, der die Größe unserer Erdkugel bestimmt hat. Seine Methode zum Auffinden von Primzahlen heißt heute noch das «Sieb des Eratosthenes».
Wir wollen mit ihm die ersten Primzahlen bestimmen. Dazu schreiben wir alle Zahlen von 1 bis 100 in eine Tabelle. Nun beginnen wir bei der zweiten Zahl, also der 2, und unterstreichen nach ihr jede zweite Zahl. Als nächstes fangen wir bei der 3 an und unterstreichen nach ihr jede dritte. Auch schon unterstrichene Zahlen zählen wir mit. Wenn wir bei der 4 angelangt sind und von ihr aus jede vierte Zahl unterstreichen wollen, merken wir, dass dies nicht nötig ist, denn diese Zahlen wurden schon beim Durchgang mit der 2 erfasst. Also fahren wir mit der 5 fort und zählen von ihr an jede fünfte Zahl. Um die 6 brauchen wir uns nicht zu kümmern, die Zahlen sind schon unterstrichen. Bei der 7 stoßen wir wieder auf nichtunterstrichene Zahlen. Abbildung unten zeigt das Ergebnis. Man kann sich leicht überlegen, dass das Streichen von Zahlen bis zu Primzahlenabständen von nicht größer als 7 genügt, um alle Primzahlen unter 100 zu erhalten. Der Vergleich mit unserer Primzahlentabelle bestätigt, dass die hier nicht unterstrichenen Zahlen genau die Primzahlen unter 100 sind. Die 1 steht zwar noch am Anfang unserer Tabelle, doch wird sie nicht zu den eigentlichen Primzahlen gezählt, sie wird als Primzahl nicht ernst genommen. Wollten wir höhere Primzahlen finden, müssten wir von Anfang an eine längere Zahlenreihe hinschreiben und neu mit dem Unterstreichen beginnen.

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

Bestimmung von Primzahlen mit dem Sieb des Eratosthenes.

Große und sehr große Primzahlen

1903 war die größte bekannte Primzahl 2 305 843 009 213 693951. Waren früher so große Primzahlen nur vereinzelt bekannt, so brachte der amerikanische Mathematiker Derrick Norman Lehmer im Jahre 1914 eine vollständige Liste bis hin zur Primzahl 10006721 heraus. Nachfolgend ein kleiner Ausschnitt aus seinem umfangreichen Tabellenwerk

  • 9890601
  • 9890623
  • 9890641
  • 9890643
  • 9890661
  • 9890677
  • 9890689
  • 9890697

die Primzahlen zwischen 9890600 und 9890700 nach Lehmer

Die größte bis November 1996 mit Computern gefundene Primzahl hat 420 921 Stellen, doch wir wissen bereits, dass es danach noch beliebig weitergeht.

Primzahlberechnung

Es wäre schön, wenn man statt des mühsamen Siebens eine Formel hätte, die der Reihe nach alle Primzahlen liefert. Die folgende Hörschrift lässt uns hoffen, ich will sie formulieren wie die Zahlenspiele unserer Kindheit: «Denk dir 'ne Zahl, zieh 1 ab, multipliziere sie mit der gedachten Zahl, und zähle 41 dazu!» Probieren Sie es, und beginnen Sie mit der 1. Das Ergebnis ist 41, denn 0 x 1 + 41 = 41 - eine Primzahl! Die 2 als nächste Zahl ergibt 43, wieder eine Primzahl! Aus der 3 wird 47, aus der 4 wird 57 - weitere Primzahlen! Durch Vergleich mit der Tabelle erkennen wir aber auch, dass in der Reihe Primzahlen ausgelassen werden. Es fehlen nicht nur diejenigen unter 41, sondern auch die 53 erhalten wir nicht. Wenn diese Regel nicht alle Primzahlen liefert, führt sie dann wenigstens stets zu einer Primzahl? Nehmen wir die 12. Das Ergebnis ist 173, Primzahl. Jetzt die 20, sie liefert 421, ebenfalls eine Primzahl! Weiter zu 30 und 40, sie liefern 911 und 1601, wieder zwei Primzahlen.
Haben wir die Weltformel der Primzahlen in Händen? Die Enttäuschung beginnt bei der 41, die als Ergebnis die Zahl 1681 liefert - Pech, das ist keine Primzahl, denn 1681 = 41 x 41. Es gibt eben keine Formel, nach der man die Primzahlen der Reihe nach berechnen kann.
Unter der Zahl 100 gibt es fünfundzwanzig Primzahlen, aber nur vierzehn liegen im gleich großen Bereich zwischen 900 und 1000. Diese Abnahme der Primzahlendichte nach oben ist unregelmäßig. Zwischen 500 und 600 liegen nur dreizehn. Im Bereich von 10 Millionen findet man unter hundert aufeinanderfolgenden Zahlen meist weniger als zehn Primzahlen. So liegen zwischen 9921400 und 9 921500 nur sechs Primzahlen und zwischen 9 893 200 und 9 893 300 gar nur drei. Die Mathematiker haben im 19. Jahrhundert das Gesetz gefunden, nach dem im Bereich der Primzahlen die Luft nach oben dünner wird, doch dieses Gesetz sagt uns nicht, welche Zahl eine Primzahl ist und welche nicht.

     

Marin Mersenne

die Pseudoprimzahlen

Pierre de Ferma

Es treten weitere Merkwürdigkeiten in der Verteilung der Primzahlen auf. Sehen wir uns noch einmal die Tabelle der Abbildung unten an. Da gibt es immer wieder aufeinanderfolgende Zahlen, die sich um nur 2 unterscheiden. Näher können sie nicht zusammenrücken, denn von zwei Zahlen, die sich nur um 1 unterscheiden, ist eine gerade. Wenn sie nicht die 2 selbst ist, dann ist sie keine Primzahl. Ist der Abstand zwischen zwei Primzahlen gleich 2, so nennt man sie Primzahlenzwillinge. In der Tabelle der Abbildung 12.7 erkennen wir 213, 517, 11113, 17119. Man könnte glauben, dass es
nun ist für Computer die Aufgabe, die ersten 1000 zu finden noch nicht gerade schwierig - es ist auch nicht schwierig, eine 100-stellige Zahl zu prüfen, ob sie den eine Primzahl sei - aber alle hundertstelligen zu finden, kann schon zeitkomplex werden

Zeitkomplexität

für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich - Beispiel: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 usw.
... hier schon mal vorab die Primzahlen bis 10007 - aber wie findet man diese?

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, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, ... .


2. Hintergründe, Zusammenhänge - Einordnung in Klassen history menue scroll up

Für kleine Mengen M ist das Problem  in seiner Lösung empirisch durch Ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten. Es sei denn, wir versuchen, neue Wege zu gehen und finden effizientere Algorithmen.
       

einfachster und rechenintensivster Primzahltester nach dem Bute-Force-Verfahren

einfachster und rechenintensivster Primzahltester nach dem Bute-Force-Verfahren

für die Suche großer Primzahlen ereichen wir schnell die Zeitkomplexität  
Achtung - dies ist nur ein Primzahltester - hilft aber vielleicht auch schon weiter ;-)

das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen

das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen

 


3. Lösungsalgorithmen history menue scroll up
Vom einfachsten Verfahren bis hin zu komplexer Mathematik ist alles möglich. Den Anfang machen simple Techniken, die für jeden einfach nachvollziehbar sind. Wir suchen die Primzahlen dadurch, dass wir der reihe nach durch alle Zahlen größer 2 und kleiner der Zahl selbst ganzzahlig dividieren. Ergibt sich bei keiner Division ein Rest von 0, so heben wir eine Primzahl gefunden. Danach verbessern wir schrittweise das Verfahren und zeigen auch neue Ideen auf.

Methode 1: Einsatz purer dummer Gewalt - das ergibt aber immerhin für kleine Zahlen in vertretbarem Zeitaufwand vollkommen korrekte Lösungen:

      Boolean-Test-Variable gefundende Primzahlen Zähler für Divisionen
      false 2 0
3 3 : 2 = 1 Rest 1 false   1
4 4 : 2 = 2 Rest 0 true   2
  4 : 3 = 1 Rest 1 true 3 3
5 5 : 2 = 2 Rest 1 false   4
  5 : 3 = 1 Rest 2 false 5 5
  5 : 4 = 1 Rest 1 false   6
6 6 : 2 = 1 Rest 1 false   7
  6 : 3 = 2 Rest 0 true   8
  6 : 4 = 1 Rest 2 true   9
  6 : 5 = 1 Rest 1 true   10
7 7 : 2 = 3 Rest 1 false   11
  7 : 3 = 2 Rest 1 false   12
  7 : 4 = 1 Rest 3 false   13
  7 : 5 = 1 Rest 2 false   14
  7 : 6 = 1 Rest 1 false 7 15
8 8 : 2 = 4 Rest 0 false/true   16
  8 : 3 = 2 Rest 2 true   17
  8 : 4 = 2 Rest 0 true   18
  8 : 5 = 1 Rest 3 true   19
  8 : 6 = 1 Rest 2 true   19
  8 : 7 = 1 Rest 1 true   20
9 9 : 2 = 4 Rest 1 false   21

Brute-Force-Angriffe

for i:=2 to bereich do
begin{begin of for1}
  test:=false;{Annahme, dass aktuelle Zahl keine Primzahl}
  for j:=2 to i-1 do
  begin{begin of for2}
    if i mod j=0
    then
    begin{begin of then}
      test:=true;
    end;{end of then}
  end;{end of for2}
  if test=false
  then
  begin{begin of then}
    ListBox1.Items.Add(IntToStr(i))
  end;{end of then}
end;{end of for1}

Brute-Force-Methode beim Herausfinden der ersten 37434 Primzahlen

Brute-Force-Methode beim Herausfinden der ersten 37434 Primzahlen

... wenn Rechenzeit vorhanden und hinreichend Rechenleistung, dann führt dieses Verfahren zu korrekten Lösungen - nur wird das gesamte Rechnersystem lahm gelegt und das Verfahren ist unintelligent und vollkommen unlogisch
Fall 1: wir dividieren die zu untersuchende Zahl durch alle ihre Vorgänger größer 1 - geht diese Division in keinem Falle ganzzahlig auf, handelt es sich um eine Primzahl
Fall 2: wir tun das, was zwingend ist: wir verwenden zum Test aber ausschließlich die ungeraden Zahlen - dieser kleine logische Schritt reduziert die zu untersuchende Menge um glatt die Hälfte!!!
Fall 3: wir dividieren die zu untersuchende ungerade Zahl durch alle ihre Vorgänger bis zur Hälfte der zu untersuchenden Größe größer 1 - geht diese Division in keinem Falle ganzzahlig auf, handelt es sich um eine Primzahl
Fall 4: wir gehen nur bis zur Quadratwurzel der zu untersuchenden ungeraden Zahl - geht dies nie ganzzahlig auf, so handelt es sich um eine Primzahl
Fall 5: nur ungerade Zahlen teilen wir durch alle bisher als Primzahlen erkannten kleineren Zahlen - geht das nie ganzzahlig auf, so haben wir eine weitere Primzahl gefunden
Fall 6: Sieb des Eratosthenes:
  • 2 wird als erste erkannte Primzahl gesetzt
  • alle Vielfachen der jeweils aktuell erkannten Primzahl werden markiert - sie sind somit von jeder weiteren Untersuchung ausgeschlossen
  • die nächst größere nicht markierte Zahl nach der gerade verwendeten Primzahl ist die nächste erkannte Primzahl
  • die aktuell erkannten Primzahlen müssen in einer äquivalenten Datenstruktur gesammelt werden
Fall 7: Philipp Oehme hat noch eine interessante Idee mit der sieben ins Spiel gebracht ;-)    (das muss aber noch gecheckt werden) - ... wir kommen mit solchen Vermutungen gefährlich nahe den Mersienne-Primzahlen

Eratosthenes von Kyene

Pierre de Fermat

kleiner Fermat'scher Satz oder auch kleiner Fermat


4. Programmvorschläge history menue scroll up

Hier können wir dereinst nur das wohlgemerkt selbst geschriebene HERON-Verfahren präsentieren. Alle oben beschriebenen Verfahren, Algorithmen und Programme sind Schritte auf dem Weg zum Ziel.
 


5. Zusammenfassung history menue scroll up

 

Arndt Brünner's Primzahlseite


6. Weiterführende Informationen history menue scroll up

 

die Zahlenteiler

GGT

KGV

die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-)

die Pseudoprimzahlen

Quersummenermittlung

   

die Primzahl-Zwillingssuche

der Kaprekar Algorithmus

die befreundeten Zahlen

das 153-Problem - Narziß-Zahlen

die Schmidtzahlen

Pythagoräische Tripel

Ulam-Spirale

die Polynomzahlen

Pascal-Zahlen

die Goldbach-Vermutung

das Palindrom Spiegelsummen-Problem

die Perfect Numbers

das Autoquadratzahlenproblem

     
 


7. Links zum Thema history menue scroll up

Obwohl von immenser Bedeutung für die gesamte Informatik, wird in der Literatur relativ wenig zu den Primzahlen ausgesagt und mit den angegebenen Beispielen und der Schulmathematik eher der Such nach den "kleinen" Primzahlen Rechnung getragen. Von enormer praktischer Bedeutung sind jedoch die großen Primzahlen.
http://www.gm.nw.schule.de/~gymwiehl/prim/primfind.htm#KleinePrim
http://www.matheprisma.uni-wuppertal.de/Module/Primz/


8. Verwandte Themen history menue scroll up

Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.

das 8-Dame-Problem

des Cliquen-Problem

Domino-Problem

das Entscheidbarkeitsproblem

das Erfüllbarkeitsproblem

die Fibonacci-Zahlen

das Flaggenproblem

das Halteproblem

das Hamilton-Problem

das K-Farben-Problem

der Kaprekar-Algorithmus

die Magischen Quadrate

das PASCAL'sche Dreiecksproblem

das Philosophenproblem

das Königsberger-Brückenproblem

das Post'schen Korrespondenzproblem

das Rundreiseproblem

das Springer-Problem

die Türme von Hanoi

das Wortproblem

das Wüstenfit-Problem

das 153-Problem

   

Worst-Case-Denken

Algorithmentheorie

Komplexität, Mächtigkeit und Aufwand

Praktische Elementaralgorithmen

Lösbarkeit und Problemlösungsstrategien

Klassische algorithmisch lösbare Probleme

Zufall und Computer

Graphentheorie

Petri-Netze

Informationsbegriff

Logo für die Signale

Nachrichten

Wissen

Systembegriff

Modellbegriff

Simulation

Denken und Sprache

Zahlen, Daten und Datentypen

Gegenläufigkeit und Verklemmung

Pattern-Matching

 



zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost am 24. Dezember 2007

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)