Cryptography Reference
In-Depth Information
during the previous steps. At the end, the positions corresponding to the remaining
zeros give the primes in the list.
> Eratosthenes := proc(n)
local s, f, a, i, j, k;
s := floor((isqrt(n)+1)/2);
f := floor((n+1)/2);
a := Array(1..f);
a[1]:=2;
for i from 2 to s do
if a[i] = 0 then
j := 2*(iˆ2-i)+1;
ArrayTools:-Fill(1,a,j-1,2*i-1);
end if;
end do;
for i from 2 to f do
if a[i] = 0 then
a[i]:= 2*i-1
end if;
end do;
convert(subs(1=NULL,a),list);
end:
For example, the 10 primes preceding 3000000 (Gauss computed all the primes
up to 3000000, so these were presumably the last ones computed by him) are the
following:
> Eratosthenes(3000000)[-10 .. -1];
[2999873,2999879,2999897,2999903,2999911,2999921,2999933,2999951,2999957,2999999]
Although the sieve can be used as a primality test, it is clearly not a very efficient
one due, among other things, to the fact that it achieves much more than required: to
test for the primality of
n
we have to compute all the primes
n
and check whether
n
is among them! It is also clear that the sieve requires a lot of memory (more than 20
MB for the precedingMaple computation, where
n
is rather small). The complexity of
the algorithmcan be estimated as follows, assuming that all arithmetic operations take
constant time which is reasonable in view of the fact that the numbers involved will
be machine-size integers—otherwise the memory requirements would be enormous.
The number of crossings off for each prime
p
is
≤
n
p
, so that the total number is
p
≤
√
n
n
p
. From [180, Theorem 5.10] it follows that
n
p
=
n
ln ln
n
+
O
(
n
),
p
≤
n
and this gives for the algorithm a running time estimate of
O
.This
complexity is exponential but, on the other hand, the space requirements of the
algorithm are even more daunting. Without going into details, we remark that, by
the PNT (see Examples 2.1 or Theorem 6.2), the number of primes less than a
given integer can be approximated by the logarithmic integral, given in Maple by the
function
Li
so that, for example, there are approximately
(
n
len
(
len
(
n
)))
> Li(2.ˆ1024);
2.536315701*10ˆ305
