View Single Post
Old 2005-12-06, 12:30   #7
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by akruppa
Is resieving worthwhile for very small primes? It seems to me that those would cause a large number of sieve locations being invesigated while having a low probability of hitting a location marked as smooth (a small prime dividing an integer does not increase the probability of that integer being smooth by much, unlike larger primes). Maybe only resieve by primes between some lower and upper bound?

This is what both my QS and lattice siever do. One of the algorithm
parameters is a TRIAL_DIVISION_CUTOFF. If p is smaller, I trial divide.
If larger, I resieve. This also cuts down on space requirements.

Experimentation is need to determine the best value for this cutoff; it
is implementation dependent and *strongly* depends on the speed of the
integer division hardware on one's machine.
R.D. Silverman is offline   Reply With Quote