First of all, when we find a new prime *m* we should append the * square* *m*^{2} 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 *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*_{1} < *s*_{2} < ^{ ... } < *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*_{1}; 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.