Next: 4.3 Combinations of the
Up: 4 Primes and Composites
Previous: 4.1 Eratosthenes' sieve
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 p2 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 x2 > N, we check for the primality
of N as follows. We run through the sequence l, dividing N by
the primes li to obtain
N = qili + ri. If ri is zero then N
is not a prime and we stop. If qi < li, then li2 > N so have
checked enough prime factors to show that N is a prime and we stop.
Kapil Hari Paranjape