Die Primzahlsuche

Letztmalig dran rumgefummelt: 29.04.25 19:32:49

	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 inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.
	Primzahlen sind das Unkraut im Garten der Zahlen Primzahlen sind die Juwelen in der Krone der Zahlen (Carl Friedrich Gauß)
	... Ishango-Knochen
	Einfacher Primzahltest - Annahme wahr Einfacher Primzahltest - Annahme falsch Einfacher Primzahltest - Division ungerade Zahlen Primzahltest - Division ungerade Zahlen bis Wurzel 2 das Feststellen, ob eine Zahl eine Primzahl ist, mit Annahme=true ... zum Entpacken als vollständiges ZIP-Archiv ... Unit vom 19.6.2023 das Feststellen, ob eine Zahl eine Primzahl ist, mit Annahme=false ... zum Entpacken als vollständiges ZIP-Archiv ... Unit vom 19.6.2023 das Feststellen, ob eine Zahl eine Primzahl ist,mit ungeraden Zahlen ... zum Entpacken als vollständiges ZIP-Archiv ... Unit vom 19.6.2023 das Feststellen, ob eine Zahl eine Primzahl ist, bis Wurzel 2 der Testzahl ... zum Entpacken als vollständiges ZIP-Archiv ... Unit vom 19.6.2023
	Test-Variable auf True im Start Test-Variable auf False im Start das Feststellen, ob eine Zahl eine Primzahl ist ... Unit vom 19.6.2023 das Feststellen, ob eine Zahl eine Primzahl ist ... Unit vom 19.6.2023

1. Problembeschreibung

	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 ... die Primzahlen bis zu 1000 - das sind 167 Primzahlen in diesem Bereich 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.
	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

	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.
	Produkte zweier großer Primzahlen Zerlegen von ganzen Zahlen in Primfaktoren einfachster und rechenintensivster Primzahltester nach dem Brute-Force-Verfahren einfachster und rechenintensivster Primzahltester nach dem Bute-Force-Verfahren Primzahl-Produkt Primzahlfaktorisierung
	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

	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 - Sieb des Eratosthenes:
	Fall 7: Teilbarkeitsregeln der 3, 5 sowie 7 anwenden
	Eratosthenes von Kyene Pierre de Fermat kleiner Fermat'scher Satz oder auch kleiner Fermat

4. Programmvorschläge

	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.
	Die einzelnen Anwendungen werden durch das Einschreiben von Teilergebnissen in WINDOWS-Komponenten etwas ausgebremst - der reine Algorithmus ist definitiv viel schneller!
	Lösung ohne ein Ausschluss-Verfahren Lösung mit Test nur ungerader Zahlen größer 2 bis n Lösung mit mit Test nur ungerader Zahlen größer 2 bis n und Test nur mit Divisin bis n/2   Lösungsalgorithmus ohne Raffinessen das Feststellen, ob eine Zahl eine Primzahl ist, ist nicht trivial für große Zahlen ... zum Entpacken als vollständiges ZIP-Archiv ... Workflow für die Anwendung von oben vom 24.5.2023 Lösungsalgorithmus mit einfachsten Ausslussverfahren das Feststellen, ob eine Zahl eine Primzahl ist, ist nicht trivial für große Zahlen ... zum Entpacken als vollständiges ZIP-Archiv ... Workflow für die Anwendung von oben vom 2.6.2023 Lösungsalgorithmus mit bereits 2 Ausschlussverfahren das Feststellen, ob eine Zahl eine Primzahl ist ... zum Entpacken als vollständiges ZIP-Archiv ... Workflow für die Anwendung von oben vom 4.6.2023 testet alle Vorgänger von n größer 1 ineffizienteste Lösung maximaler Aufwand und somit Rechenzeit testet alle ungeraden Vorgänger von n größer 1 noch immer sehr ineffiziente Lösung sehr hoher Aufwand und somit Rechenzeit testet nur ungerade Zahlen arbeitet bis maximal zur Quadratwurzel von n schließt bereits durch 3, 5 sowie 7 teilbare Zahlen n aus
	Lösung mit mit Test nur ungerader Zahlen größer 2 bis n und Test nur mit Divisin bis zur Quadratwurzel non n   Lösung mit mit Test nur ungerader Zahlen größer 2 bis n und Test nur mit Divisin bis zur Quadratwurzel non n Lösung mit bereits vielen eingebauten Ausschluss-Verfahren   Lösungsalgorithmus mit vielen Raffinessen das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen ... zum Entpacken als vollständiges ZIP-Archiv ... Workflow für die Anwendung von oben vom 5.6.2023   Lösungsalgorithmus mit vielen Raffinessen das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen ... zum Entpacken als vollständiges ZIP-Archiv ... Workflow für die Anwendung von oben vom 24.5.2023 testet alle Vorgänger von n größer 1 ineffizienteste Lösung maximaler Aufwand und somt Rechenzeit   testet nur ungerade Zahlen arbeitet bis maximal zur Quadratwurzel von n schließt bereits durch 3, 5 sowie 7 teilbare Zahlen n aus

5. Zusammenfassung

	Arndt Brünner's Primzahlseite

6. Weiterführende Informationen

	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

	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

	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