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 $\sqrt{N}$, 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 m² 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 $\sqrt{N}$. 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 $\mathbb {Z}$/M$\mathbb {Z}$.

After we exhaust the given list l without obtaining q_i < l_i 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 s₁ < s₂ < ^... < s_r 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 s_t. After we have exhausted the list l we try l_{k + 1} = l_k + (s_{t + 1} - s_t). Then we can try l_{k + i + 1} = l_{k + i} + (s_{i + 1} - s_i) in succession, with the understanding that the successor s_{r + 1} or s_r is M + s₁; and more generally s_{ar + b} = aM + s_b.

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.