Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:17:55
Deutsch
19.Sep 2021

Sieve of Ulam (vertical)

Have a look at the sieve of the Ulam (horizontal), if you are not familiar with it.

This is another idea to calculate primenumbers:

By taking 2*3*5*7*11*13 as modul, you could negligate more than 4/5 of the numbers.
These numbers can be disregarded.

Size of Modul Used primes Comparison possible prime numbers in percent
2 Modul 2 1/2 50%
6 Modul 2,3 2/6 33%
30 Modul 2,3,5 8/30 26%
210 Modul 2,3,5,7 48/210 22,4%
2.310 Modul 2,3,5,7,11 480/2.310 20,7%
30.030 Modul 2,3,5,7,11,13 5.760 / 30.030 19,2%
510.510 Modul 2,3,5,7,11,13,17 92.160 / 510.510 18,1%
9.699.690 Modul 2,3,5,7,11,13,17,19 1.658.880 / 9.699.690 17,1%
223.092.870 Modul 2,3,5,7,11,13,17,19,23 36.495.360 / 223.092.870 16,4%
6.469.693.230 Modul 2,3,5,7,11,13,17,19,23,29 1.021.870.080 / 6.469.693.230 15.8%
200.560.490.130 Modul 2,3,5,7,11,13,17,19,23,29,31 30.656.102.400 / 200.560.490.130 15.3%
7.420.738.134.810 Modul 2,3,5,7,11,13,17,19,23,29,31,37 1.103.619.686.400 / 7.420.738.134.810 14.9%

This is one of the advantage of the sieve of Ulam vertikal in comparison to the sieve of Eratosthenes.

Example:
let us take 30 as modul.

There are 8 sequences which can be examine for primes seperately:
1+30n, 7+30n, 11+30n, 13+30n, 17+30n, 19+30n, 23+30n, 29+30n

( The sequences 3+30n, 5+30n, 9+30n, 15+30n, 21+30n, 25+30n can be disregarded
because they do not contain primes (gcd (3+30n, 30) > 1). )

The primes on the 8 sequences occur periodically,
that means if (a+30n) | p then (a+30(n+p)) | p

Algorithm

First the sequence is calculated, that means list [i]:=i*30+rest for i from 0 to liste_max

Secondary the "start numbers" are calculated:
The multiplication of two primes < 30 which have the same rest concerning the examing sequence are calculated

Let rest:=1
if a*b = rest mod 30 then b = rest * a^(-1) mod 30
If a and b are primes then the list is sieved out by them.
The combination of a*b occurs twice, if a element of P < 30.( a*b=b*a )
With the condition b>a only one combination is used.
If a=b only one sieving is made.

The sieving is made by division from list [i] / p as often as possible.
Therefore one division and a mod p is used.

At last the list is examined by looking up, if liste[i] = i*30+rest. If liste[i]=i*30+rest then it is a prime, sieves the increasing list and is counted.
If liste[i]>1 then it is a prime which sieve the increasing list, too.

The numbers on the sequences are sorted, that means
if list is sieved by the calculation of the start numbers
only primes occurs at first on the list which sieve the remaining list.

Implementation
  • // Choose the index mod 30 for the sieve
    rad:=30;

    //  Choose the size of the list array.
    liste_max:=10000;

    // All numbers n < rad with gcd (n, rad)=1)
    sequence := {1, 7, 11, 13, 17, 19, 23, 29};

    // All numbers p < rad with p is prime
    primes :={7, 11, 13, 17, 19, 23, 29};

    sieving:=proc (start, p)
    begin
      while start <= liste_max do
         repeat
            liste [start]:=liste [start] / p;
         until (liste [start] mod p > 0) end_repeat;
         start:=start+p;
      end_while;
    end;

    // Initialisierung
    for t from 1 to nops (sequence) do
       anz:=0;
       modul:=sequence[t];
       print ("Modul = ", modul);

       // Fill the array with values.
       for i from 0 to liste_max do
          liste [i]:=i*rad+modul;
       end_for;

    // Calculation of the "start points", a*b = modul mod rad
       for i from 1 to nops (primes) do
          a:=primes[i]; 
          b:=modul*a^(-1) mod rad;
          
          // Sieving if a and b are primes
          if (contains (primes, b)=TRUE) then
             // The combination of a*b occurs twice, 
             // but for the sieving only one combination is needed
             if b>=a then
                start:=(a*b - modul)/rad;
                sieving (start, a);
                if a<>b then
                   sieving (start, b);
                end_if;
             end_if;
          end_if;
       end_for;

       // Printing the prime numbers
       for i from 0 to liste_max do
          if liste [i]=i*rad+modul then
             if liste [i]=i*rad+modul then
                // Printing the primes and counting
                // print (liste[i]);
                anz:=anz+1;
             end_if;
          end_if;

          a:=liste [i];
          if a>1 then
            // Control, only for testing
            /* if isprime (a)=FALSE then
                 print (ifactor (a));
                 return (1);
               end_if;
            */

            // Sieving      
            start:=i+a;
            sieving (start, a);
          end_if;
       end_for;
       print ("Anzahl von Primzahlen", anz);
    end_for;




                               "Modul = ", 1

                       "Anzahl von Primzahlen", 3231

                               "Modul = ", 7

                       "Anzahl von Primzahlen", 3253

                              "Modul = ", 11

                       "Anzahl von Primzahlen", 3248

                              "Modul = ", 13

                       "Anzahl von Primzahlen", 3261

                              "Modul = ", 17

                       "Anzahl von Primzahlen", 3268

                              "Modul = ", 19

                       "Anzahl von Primzahlen", 3227

                              "Modul = ", 23

                       "Anzahl von Primzahlen", 3250

                              "Modul = ", 29

                       "Anzahl von Primzahlen", 3260