Bestimmung oder Berechnung von Primzahlen in der Geschichte

Sieb des Eratosthenes (ca. 275 – 194 v. Chr.)

Sieb Eratosthenes

 

 

Es bleiben die Primzahlen übrig:

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

 

 

 

  

  

Mersenne-Zahlen Mp = 2p – 1, p Primzahl, Marin Mersenne (1588 – 1648)

p     2p – 1    

2      3, prim

3      7, prim

5      31, prim

7      127, prim

11     2047 = 23·89

13     8191, prim

17     131071, prim

19     524287, prim

7 Primzahlen 2p – 1 von 8 Primzahlen p

8 Primzahlen 2p – 1 von 16 Primzahlen p

20 Primzahlen 2p – 1 von 602 Primzahlen p

Die Anzahl der Mersenne-Primzahlen nimmt mit zunehmendem p sehr schnell ab.

 

 Fermat-Zahlen fermat-1  n ganze Zahl ≧ 0, Pierre de Fermat (1607 – 1665)

fermat-2

0      3, prim

1      5, prim

2      17, prim

3      257, prim

4      65537, prim

5      4294967297 = 641·6700417

Fermat vermutete 1640, dass dies auf alle Fermat-Zahlen zutreffe. Dies wurde aber 1732 von Leonhard Euler widerlegt, indem er den Teiler 641 für die 6. Fermat-Zahl fand.

 

Formeln von Leonhard Euler (1707 – 1783) zur Berechnung von Primzahlen

Eulers Formel: n2 + n + 41

tab_euler-1

Erzeugt Primzahlen für n = 0 bis 39.

582 Primzahlen für n = 0 bis 1000.

Die Formel liefert für die Primzahl 41 die besten Ergebnisse.

 

Euler-Polynom: n2 – 79n + 1601

tab_euler-2

Erzeugt Primzahlen für n = 0 bis 79.

602 Primzahlen für n = 0 bis 1000.

 

Dirichletsche Primzahlsatz (1837),  Peter G. L. Dirichlet (1805 – 1859)

Sind a und m teilerfremde natürliche Zahlen, d.h. mit dem größten gemeinsamen Teiler ggT(a,m) = 1, dann kommen in der arithmetischen Folge a, a + m, a + 2m, a + 3m, . . . unendlich viele Primzahlen vor.

Beispiele:

a = 1, m = 3

1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, …

a = 2, m = 5

2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 87, 92, 97, 102, …

Primzahlen sind rot dargestellt.

 

Weitere Formen der Primzahlberechnung

Primzahlen der Form 6n +/- 1

6n + 1:

tab_6n+1

51 Primzahlen für n = 2 bis 100 .

384 Primzahlen für n = 2 bis 1000.

6n – 1:

tab_6n-1

57 Primzahlen für n = 2 bis 100.

397 Primzahlen für n = 2 bis 1000.

 

Primzahlen der Form n2 + 1

tab_n²+1

 33 Primzahlen für gerades n = 2 bis 200.

 208 Primzahlen für gerades n = 2 bis 2000.

 

Primzahlen der Form (n+1)3 – n3 

tab_(n+1)³-n³

42 Primzahlen für n = 1 bis 100.

263 Primzahlen für n = 1 bis 1000.

 

Pierpont-Primzahlen der Form 2n · 3m + 1, James Pierpont (1866 – 1938)

31 Primzahlen für n = 1 bis 10 und m = 1 bis 10.

 

Primzahlenprodukt + 1 (PP)

2 + 1 = 3, prim

2 · 3 + 1 = 7, prim

2 · 3 · 5 + 1 = 31, prim

2 · 3 · 5 · 7 + 1 = 211, prim

2 · 3 · 5 · 7 · 11 + 1 = 2311, prim

2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509

2 · 3 · 5 · 7 · 11 · 13 · 17 + 1 = 510511 = 19 · 97 · 277

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 + 1 = 9699691 = 347 · 27953

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 + 1 = 223092871 = 317 · 703763

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 + 1 = 6469693231 = 331 · 571 · 34231

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 + 1 = 200560490131, prim

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 + 1 = 7420738134811 = 181 · 60611 · 676421

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 + 1 = 304250263527211 = 61 · 450451 · 11072701

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 · 43 + 1 = 13082761331670031 = 167·78339888213593

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 · 43 · 47 + 1 = 614889782588491411 = 953·46727·13808181181

2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 · 43 · 47 · 53 + 1 = 32589158477190044731 = 73·139·173·18564761860301

6-mal prim von 25 PP sind 24,0 %.

9-mal prim von 300 PP sind 3,0 %.

 

Ungerade Primzahlensummen (uPS)

2 3  = 5, prim

2 + 3 + 5 + 7  = 17, prim

2 + 3 + 5 + 7 + 11 + 13  = 41, prim

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19  = 77 = 7 · 11

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29  = 129 = 3 · 43

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37  = 197, prim

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43  = 281, prim

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53  = 381 = 3 · 127

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61  = 501 = 3 ·167

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71  = 639 = 32 · 71

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79  = 791 = 7 · 113

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89  = 963 = 32 · 107

5-mal prim von 12 uPS sind 41,7%.

52-mal prim von 300 uPS sind 17,3 %.

 

Adrian Stoica-Vermutung (2004)

Für jede ungerade natürliche Zahl n > 1 existieren zwei natürliche Zahlen x und y mit x + y = n, so dass gilt x² + y² ist Primzahl.

Beispiele:

n = 9                        

x  y    x²+y²

2  7    53, prim 

4  5    41, prim 

n = 15

1  14   197, prim 

2  13   173, prim 

4  11   137, prim  

7    8   113, prim   

 

Bemerkung:

Das Berechnen von Primzahlen mit Hilfe einer Formel hat geschichtliche Bedeutung.

Auch komplexe Formeln, wie die von Willans oder Jones, haben nur theoretische Bedeutung.

Primzahlen werden mit Hilfe von Computerprogrammen berechnet.

 

Primzahl-Programm in Python für Primzahlen von 2 bis 5000:

def primzahl(n):

    if n <= 1:

        return False

    for i in range(2, int(n**0.5) + 1):

        if n % i == 0:

            return False

    return True

primzahlen = [x for x in range(2, 5000) if primzahl(x)]

print(primzahlen)

 

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

Zurück
Zurück zur Startseite