The theory of numbers, by Robert D. Carmichael ...

ELEMENTARY PROPERTIES OF INTEGERS

11

must finally arrive at a prime factor of m. From this conclusion the theorem follows immediately.
Eratosthenes has given a useful means of finding the prime
numbers which are less than any given integer m. It may be
described as follows:
Every prime except 2 is odd. Hence if we write down every
odd number from 3 up to m we shall have in the list every prime
less than m except 2. Now 3 is a prime. Leave it in the list;
but beginning to count from 3 strike out every third number
in the list. Thus every number divisible by 3, except 3 itself,
is cancelled. Then begin from 5 and cancel every fifth number. Then begin from the next uncancelled number, namely
7, and strike out every seventh number. Then begin from
the next uncancelled number, namely II, and strike out every
eleventh number. Proceed in this way up to m. The uncancelled numbers remaining will be the odd primes not greater
than m.
It is obvious that this process of cancellation need not be
carried altogether so far as indicated; for if p is a prime greater
than,/m, the cancellation of any pth number from p will be
merely a repetition of cancellations effected by means of another
factor smaller than p, as one may see by use of the following
theorem.
II. An integer m is prime if it has no prime factor equal to
or less than I, where I is the greatest integer whose square is
equal to or less than m.
Since m has no prime factor less than I, it follows from
theorem I that it has no factor but unity less than I. Hence,
if m is not prime it must be the product of two numbers each
greater than I; and hence it must be equal to or greater than
(I+I)2. This contradicts the hypothesis on I; and hence
we conclude that m is prime.
EXERCISE
By means of the method of Eratosthenes determine the primes less than
200.