Next: 4.4 Compositeness Tests Up: 4 Primes and Composites Previous: 4.2 Trial division

## 4.3 Combinations of the methods

When we compare the trial division method with Eratosthenes' sieve, we see that we are only checking for divisors upto , but we are performing divisions rather than the (much simpler) additions. Thus there should be a way of improving the Eratosthenes' method.

First of all, when we find a new prime m we should append the square m2 to the list of multiples rather than 2*m; all smaller multiples of m are also multiples of smaller primes! This is not enough to speed up the sieve computation since we will still be comparing our trial prime m with all the elements in the multiple list instead of only the relevant'' ones; the list of multiples grows as fast as the list of primes, whereas the multiples we need to check against are only multiples of primes less than the square root. Thus we keep a pointer s into the list m that keeps track of where the list of squares in this list start. We do not check for multiples beyond this point. This extension of the sieve using the idea from trial division is a good way to generate lists of primes.

Trial division is then only a method to check for primality for a small set of numbers and not a method for building lists. Its one big limitation is its dependence on a list of all primes upto . We do not want to keep extending our list of primes (otherwise we may as well be generating using the sieve as above). So we can ask if we can improve trial division using ideas from the sieve.

It is possible to append a sieve'' at the end of the given list of primes l as follows. Let M the product of a the first few prime numbers (say 6 or 30 or 210). Let S be the (naturally ordered) collection of representatives between 0 and M - 1 of the units in /M.

After we exhaust the given list l without obtaining qi < li we can extend'' the trial division process by trying divisors of the form s + nM where s runs over the residue classes S and n over non-negative integers. While these divisors are not primes, they include all primes and we are at least eliminating some obvious'' repetitions.

Algorithmically, we can apply the above procedure as follows. Let s1 < s2 < ... < sr be the list of elements of S. We place the residue class modulo M of the largest element p of l (which should be larger than the factors of M!) in this list--say as st. After we have exhausted the list l we try lk + 1 = lk + (st + 1 - st). Then we can try lk + i + 1 = lk + i + (si + 1 - si) in succession, with the understanding that the successor sr + 1 or sr is M + s1; and more generally sar + b = aM + sb.

This allows us to check the primality of numbers larger than the square of p as well. However, the job of running through a long list of divisors makes trial division unsuitable for finding large prime factors. One can show that (for many numbers) trial division quickly finds small prime factors and then spends a lot of time running through the lists trying to find the larger ones.

Next: 4.4 Compositeness Tests Up: 4 Primes and Composites Previous: 4.2 Trial division
Kapil Hari Paranjape 2002-10-20