 |
Development of
Algorithmic Constructions |
09:32:41
|  | | | 20.Apr 2024
|
|
Sieb des Ulam
Folgendes Verfahren läßt sich als
Weiterentwichklung vom Sieb des Eratosthenes entwickeln:
Man kann einen
Stempel konstruieren, zum Beispiel einen 6 Stempel, der so aussieht:
6-Stempel
| 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 |
Primzahlen können nur auf den violetten
Linien liegen, da die anderen gerade oder durch 3 teilbar sind. Die Stempellänge
ergibt sich aus dem Produkt der ersten Primzahlen, also 2*3 für den 6-Stempel,
der sich dann wiederholt.
Die Zahlen, die übrig bleiben sind also
1+6i
5+6i i=0,1,2,3...
Es bleiben also 2/6 bzw. 33% Prozent der
Zahlen übrig, die man auf Prim überprüfen muß.
30-Stempel
Der 30-Stempel sieht wie folgt aus (gerade Zahlen sind nicht aufgeführt)
| 1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
25 |
27 |
29 |
| 31 |
33 |
35 |
37 |
39 |
41 |
43 |
45 |
47 |
49 |
51 |
53 |
55 |
57 |
59 |
| 61 |
63 |
65 |
67 |
69 |
71 |
73 |
75 |
77 |
79 |
81 |
83 |
85 |
87 |
89 |
| 91 |
93 |
95 |
97 |
99 |
101 |
103 |
105 |
107 |
109 |
111 |
113 |
115 |
117 |
119 |
Primzahlen können nur auf
den violetten Linien liegen. Die Zahlen lassen sich wie folgt darstellen:
1+30i
7+30i
11+30i
13+30i
17+30i
19+30i
23+30i
29+30i
i=0,1,2,3...
Es bleiben also 8/30 bzw. 26% Zahlen übrig die auf Prim
überprüft werden müssen.
Verallgemeinerung:
Es läßt sich ein Stempel konstruieren, der die Stempellänge = Produkt der ersten Primzahlen hat.
Die Startwerte sind alle Zahlen n mit gcd (n, Stempellänge)=1.
Verhalten:
| Stempelgröße |
eleminierte Primzahlen |
Verhältnis |
mögliche Primzahlen in Prozent->oo |
größte Lücke |
| 2 Stempel |
2 |
1/2 |
50% |
2 |
| 6 Stempel |
2,3 |
2/6 |
33% |
4 |
| 30 Stempel |
2,3,5 |
8/30 |
26% |
6 |
| 210 Stempel |
2,3,5,7 |
47/210 |
22,4% |
10 |
| 2.310 Stempel |
2,3,5,7,11 |
479/2.310 |
20,7% |
14 |
| 30.030 Stempel |
2,3,5,7,11,13 |
5.759 / 30.030 |
19,2% |
22 |
| 510.510 Stempel |
2,3,5,7,11,13,17 |
92.159 / 510.510 |
18,1% |
26 |
| 9.699.690 Stempel |
2,3,5,7,11,13,17,19 |
1.658.879 / 9.699.690 |
17,1% |
34 |
| 223.092.870 Stempel |
2,3,5,7,11,13,17,19,23 |
36.495.359 / 223.092.870 |
16,4% |
40 |
| 6.469.693.230 Stempel |
2,3,5,7,11,13,17,19,23,29 |
1.021.870.079 / 6.469.693.230 |
15.8% |
46 |
Abschätzung:
Die Prozentzahl gibt dabei an, wieviele Primzahlen maximal
in dem Bereich bis unendlich möglich sind.
Implementation:
m:=2*3*5*7*11*13;
m_next:=17;
s:=10;
liste_max:=s*m;
i_1:=1;
j:=1;
for i from m_next to m step 2 do
if gcd (i, m)=1 then
// Die Differnz zwischen den Primzahlen wird gespeichert
distance [j-1]:=i-i_1;
j:=j+1;
i_1:=i;
end_if;
end_for;
distance [j-1]:=2;
j_max:=j;
// Vorbesetzung
x:=1;
for k from 1 to liste_max/m-1 do
for j from 0 to j_max-1 do
// x wird um die jeweilige Distanz erhöht, und nicht jeweils nur um 2 => Geschwindigkeitsvorteil
x:=x+distance [j];
// alle Listenwerte, die gcd (m, x)=1 haben werden als mögliche Primzahlen markiert
ges_liste [x]:=1;
end_for;
end_for;
// Aussiebung
x:=1;
for k from 1 to liste_max/m-1 do
for j from 0 to j_max-1 do
// x wird um die jeweilige Distanz erhöht, und nicht jeweils nur um 2 => Geschwindigkeitsvorteil
x:=x+distance [j];
if (ges_liste [x]=1) then
// neue Primzahl gefunden
print (x);
q:=x*x;
while q<liste_max do
// Die neugefundenen Primzahlen werden ab dem Quadrat in der Liste gestrichen.
ges_liste [q]:=0;
q:=q+2*x;
end_while;
end_if;
end_for;
end_for;
Der Geschwindigkeitsvorteil durch das Addieren der Differenzen, wird aber wahrscheinlich durch den Lookup in der Tabelle mit den Differenzen zunichte gemacht.
Eine sehr schöne theoretische Überlegung ;-) .
|