Primzahl
Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und durch sich selbst teilbar ist. So sind z.B. die Zahlen 2, 3, 5, 7, 11 Primzahlen, die Zahl 10 jedoch nicht, weil sie außer durch 1 und durch 10 auch noch durch 2 und 5 teilbar ist.
Eine Verallgemeinerung des Begriffs Primzahl auf beliebige Ringe ist der Begriff des Primelementes.
Mit Ausnahme der 2 sind alle Primzahlen ungerade, denn alle geraden Zahlen lassen sich ja durch 2 teilen. Zwei aufeinanderfolgende ungerade Zahlen, die beide Primzahlen sind, heißen Primzahlzwillinge, z.B. 11 und 13.
Jede positive ganze Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen. So besteht z.B. die Zahl 1050 aus den Primfaktoren 2 · 3 · 5 · 5 · 7.
Es gibt keine größte Primzahl, sondern unendlich viele Primzahlen. Dies lässt sich mathematisch beweisen (Euklids Primzahlbeweis). Ob es auch unendlich viele Primzahlzwillinge gibt, ist nicht bekannt.
Primzahlen spielen eine wichtige Rolle unter anderem in der Kryptologie. Einige Verschlüsselungssysteme basieren darauf, dass man zwar relativ schnell große Primzahlen erzeugen und mit ihnen rechnen kann, dass es aber (noch) kein schnelles Verfahren gibt, um große Zahlen auf ihre Primfaktoren zu prüfen (große Zahlen sind Zahlen mit mehreren hundert Stellen!).
- Jede positive ganze gerade Zahl > 2 kann als Summe zweier Primzahlen dargestellt werden.
Sieb des Eratosthenes
- Der schnellste Weg alle Primzahlen bis zu einer Zahl n zu finden ist das Sieb des Eratosthenes.
- Dies gilt vor allem für alle "kleinen" Primzahlen bis zu einer Größe von 10 Millionen .
- Man listet alle ungeraden Zahlen von 3 bis n auf.
- Man streicht alle Vielfachen dieser Zahlen aus, die kleiner als oder gleich groß wie die Quadratwurzel von n sind
- Die Zahl 2, sowie die Zahlen, die nicht ausgestrichen wurden, sind Primzahlen.
Nachweis von Primzahlen
- Im Jahr 2002 fanden Manindra Agrawal, Neeraj Kayal und Nitin Saxena einen Algorithmus, nach ihnen AKS-Methode genannt, durch den sich der Nachweis, ob eine Zahl eine Primzahl ist, in Polynomialzeit durchführen lässt.
Fragen
- Warum ist die 1 keine Primzahl ?
- Antwort 1: Weil 1 eine Einheit ist (siehe Primelement).
- Antwort 2: Damit man eine eindeutige Primfaktorenzerlegung bekommt (man hätte sonst beliebig viele 1-Faktoren mit drin).
- Außerdem lautet die Bedienung, dass eine Zahl eine Primzahl ist, wenn sie durch 1 und durch sich selbst teilbar ist. Dies ist bei der Zahl 1 nicht so!
Primzahl Links
- http://www.utm.edu/research/primes/
- http://www.utm.edu/research/primes/howmany.shtml
- http://www.informatik.uni-frankfurt.de/~fp/Tools/Sieve.html
- http://home.t-online.de/home/0926161717-0002/prgsieb.htm
- Visual Basic Programm zur Berechnung von Primzahlen
Primzahlen von 1 - 10000
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.