Proof.
[Proof of Algorithm
1.2.3]
The part of the algorithm that is not clear is that
when the first element
![$ a$](img37.png)
of
![$ X$](img254.png)
satisfies
![$ a\geq \sqrt{n}$](img265.png)
,
then each element of
![$ X$](img254.png)
is prime.
To see this, suppose
![$ m$](img266.png)
is in
![$ X$](img254.png)
, so
![$ \sqrt{n} \leq m\leq n$](img267.png)
and that
![$ m$](img266.png)
is divisible by
no prime that is
![$ \leq \sqrt{n}$](img268.png)
. Write
![$ m=\prod p_i^{e_i}$](img269.png)
with
the
![$ p_i$](img270.png)
distinct primes ordered so that
![$ p_1<p_2<\ldots$](img271.png)
. If
![$ p_i>\sqrt{n}$](img272.png)
for each
![$ i$](img223.png)
and there is more than one
![$ p_i$](img270.png)
, then
![$ m>n$](img273.png)
,
a contradiction. Thus some
![$ p_i$](img270.png)
is less than
![$ \sqrt{n}$](img274.png)
,
which also contradicts our assumptions on
![$ m$](img266.png)
.
SAGE Example 1.2
The eratosthenes command implements the sieve in SAGE:
sage: eratosthenes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]