I The Sieve of Eratosthenes
As I have already said, it is possible to find if N is a prime using
trial division by every number n such that n2 ≤ N.
Since multiplication is an easier operation than division, Eratosthenes
(in the 3rd century BC) had the idea of organizing the computations
in the form of the well-known sieve. It serves to determine
all the prime numbers, as well as the factorizations of composite
numbers, up to any given number N. This is illustrated now for
N = 101.
Do as follows: write all the numbers up to 101; cross out all the
multiples of 2, bigger than 2; in each subsequent step, cross out all
the multiples of the smallest remaining number p, which are bigger
than p. It suffices to do it for p2 < 101.
Thus, all the multiples of 2, 3, 5, 7 < √101 are sifted away. The
number 53 is prime because it remained. Thus the primes up to 101 are 2, 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.
This procedure is the basis of sieve theory, which has been developed to provide estimates for the number of primes satisfying given conditions.