 # Development ofAlgorithmic Constructions

 12:17:55 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

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

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
end_for;

// Calculation of the "start points", a*b = modul mod rad
for i from 1 to nops (primes) do
a:=primes[i];

// 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
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
// 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

```