Primzahlen Zurück
Primzahl Definition Primzahllinks
Eine Primzahl ist eine ganze positive Zahl, die nur durch 1 und sich selbst ohne Rest geteilt werden kann.
Primzahlen von 1- 10000:
1,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,
Berechnungsmethode für Primzahlen Programm in Visual Basic
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 .
For example, to find all the primes less than or equal to 30, first list the numbers from 2 to 30.
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
The first number 2 is prime, so keep it (we will color it green) and cross out its multiples (we will color them red), so the red numbers are not prime.
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
The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples.
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
Now the first number left (still black) is 5, the second odd prime. So keep it also and cross out all of its multiples (25 is the only one not yet crossed out).
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
The next number left, 7, is larger than the square root of 30, so all of the numbers left are primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Notice we just found these primes without dividing.
This algorithm can be written in pseudo-code as follows
Eratosthenes(n) {a[1] := 0for i := 2 to n do a[i] := 1p := 2while p2 < n do {j := 2pwhile (j < n) do {a[j] := 0j := j+p}repeat p := p+1 until a[p] = 1}return(a)}
This method is so fast that there is no reason to store a large list of primes on a computer--an efficient implementation can find them faster than a computer can read from a disk. In fact the problem with the algorithm as presented above is not really speed (it uses O(n(log n)log log n) bit operations), but rather space (it is O(n)). So for large n we usually use a segmented sieve. However, both the time and space theoretically can be improved; for example, Pritchard's "linear segmented wheel sieve" uses O(n log n) bit operations and O(sqrt(n)/log log n) space.
References
- BH77
- C. Bayes and R. Hudson, "The segmented sieve of Eratosthenes and primes in arithmetic progression," BIT, 17 (1977) 121--127.
- Bressoud89
- D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, New York, 1989. [pseudocode implementation on page 19] [QA161.F3B73, ISBN 3-540-97040-1]
- Pritchard87
- P. Pritchard, "Linear prime-number sieves: a family tree," Sci. Comput. Programming, 9 (1987) 17-35. [Comparison of various sieves] [A comparison of recent sieves such as the sieve of Eratosthenes.]
- Riesel94
- H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics volume 126, Birkhäuser Boston, 1994. [a PASCAL implementation on page 6] [An excellent reference for those who want to start to program some of these algorithms. Code is provided in Pascal. Previous edition was vol. 57, 1985.]
Primzahlsatz
Goldbachsche Vermutung
Jede positive ganze gerade Zahl > 2 kann als Summe zweier Primzahlen dargestellt werden.
Every even n > 2 is the sum of two primes.
Goldbach wrote a letter to Euler in 1742 suggesting that every integer n > 5 is the sum of three primes. Euler replied that this is equivalent to every even n > 2 is the sum of two primes--this is now know as Goldbach's conjecture. Schnizel showed that Goldbach's conjecture is equivalent to every integer n > 17 is the sum of three distinct primes.
It has been proven that every even integer is the sum of at most six primes [Ramaré95](Goldbach suggests two) and in 1966 Chen proved every sufficiently large even integers is the sum of a prime plus a number with no more than two prime factors (a P2). In 1993 Sinisalo verified Goldbach's conjecture for all integers less than 4.1011 [Sinisalo93]. More recently Jean-Marc Deshouillers, Yannick Saouter and Herman te Riele have verified this up to 1014 with the help, of a Cray C90 and various workstations. In July 1998, Joerg Richstein completed a verification to 4.1014 and placed a list of champions online. See [Ribenboim95] and [Wang84] for more information.
http://www.utm.edu/research/primes/