## Prime number sieve

Expand Messages
• A beautifull day, i have written a quadratic sieve algorithm which produces all prime numbers up to a limit. I examine the three polynoms 4x^2+1, 2x^2+1 and
Message 1 of 1 , May 26, 2007
• 0 Attachment
A beautifull day,

i have written a quadratic sieve algorithm which produces all prime
numbers up to a limit. I examine the three polynoms 4x^2+1, 2x^2+1
and 2x^2-1. All prime numbers can be found on these tree polynoms.

I hope that my algorithm is faster then the sieve of Eratosthenes,
because the density of the primes is nearly constant concerning the
primes you can found on the polynoms.

Best greetings from the primes
Bernhard Helmes

liste_max:=100;
z:={};

siebung:=proc (stelle)
begin
while (stelle<=liste_max) do
erg:=liste[stelle];
erg:=erg /p;
while (erg mod p = 0) do
erg:=erg /p;
end_while;
liste[stelle]:=erg;
stelle:=stelle+p;
end_while;
end_proc;

// 1. Polynom 4*x^2+1
for x from 1 to liste_max do
liste [x]:=4*x^2+1;
end_for;

for x from 1 to liste_max do
p:=liste[x];
if (p>1) then
// print ("x = ", x, "Prim = ", p) ;
z:=z union {p};
siebung (x+p);
siebung (p-x);
end_if;
end_for;

// 2. Polynom 2*x^2+1

for x from 1 to liste_max do
liste [x]:=2*x^2+1;
end_for;

for x from 1 to liste_max do
p:=liste[x];
if (p>1) then
z:=z union {p};
// print ("x = ", x, "Prim = ", p) ;
siebung (x+p);
siebung (p-x);
end_if;
end_for;

// 3. Polynom 2*x^2-1

for x from 1 to liste_max do
liste [x]:=2*x^2-1;
end_for;

for x from 1 to liste_max do
p:=liste[x];
if (p>1) then
z:=z union {p};
// print ("x = ", x, "Prim = ", p) ;
siebung (x+p);
siebung (p-x);
end_if;
end_for;

print (z)

{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, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311,
313,

317, 337, 349, 353, 373, 379, 401, 419, 431, 449, 457, 461, 467,
491,

523, 541, 547, 557, 569, 577, 593, 599, 601, 607, 617, 631, 641,
647,

661, 673, 677, 683, 709, 743, 769, 827, 881, 883, 911, 937, 953,
967,

1063, 1129, 1151, 1153, 1193, 1217, 1249, 1283, 1291, 1297, 1321,
1459,

1481, 1531, 1549, 1567, 1601, 1607, 1621, 1667, 1693, 1721, 1783,
1801,

1873, 2017, 2069, 2081, 2113, 2179, 2243, 2311, 2333, 2591, 2593,
2633,

2731, 2777, 2857, 2887, 2917, 3041, 3083, 3137, 3361, 3527, 3529,
3697,

3851, 4049, 4051, 4231, 4357, 4483, 4621, 4801, 4817, 4931, 4993,
4999,

5281, 5407, 5477, 5521, 6271, 6337, 6961, 7057, 7069, 7687, 7841,
7937,

8101, 8191, 8713, 8837, 9521, 10369, 10657, 11251, 11551, 12101,
12799,

13121, 13457, 14401, 14449, 15137, 15139, 15377, 15877, 16561,
16901,

16927, 17299, 17957, 18049, 18433, 19207, 19603, 21317, 22501,
24337,

25601, 28901, 30977, 32401, 33857}
Your message has been successfully submitted and would be delivered to recipients shortly.