Inhaltsverzeichnis

Development of
Algorithmic Constructions

13:21:08
Deutsch
19.Sep 2021

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 ;-) .