** Next:** 4.3 Combinations of the
** Up:** 4 Primes and Composites
** Previous:** 4.1 Eratosthenes' sieve

If
*N* = *a*^{ . }*b* is a factoring of a number *N*, then at least one of
the numbers *a*, *b* is such that its square is not more than *N*.
Thus to check, whether *N* is a prime, it is enough to test whether it
is a multiple of prime number *p* so that *p*^{2} is not more than *N*.
This leads to the first test that does not require a list of all
primes less than *N*. Given the increasing sequence *l* of all primes
less than some number *x* so that *x*^{2} > *N*, we check for the primality
of *N* as follows. We run through the sequence *l*, dividing *N* by
the primes *l*_{i} to obtain
*N* = *q*_{i}*l*_{i} + *r*_{i}. If *r*_{i} is zero then *N*
is not a prime and we stop. If *q*_{i} < *l*_{i}, then *l*_{i}^{2} > *N* so have
checked enough prime factors to show that *N* is a prime and we stop.

Kapil Hari Paranjape
2002-10-20