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

4.2 Trial division

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 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 2002-10-20