> Whilst keeping memory requirements reasonable, we could build a
> second stage sieve to eliminate the primes 19, 23, 29 & 31 in a
> second table of size 392863. Doing this would eliminate about 15% of
> the candidates remaining from the first pass, whereas the first pass
> eliminates about 64%. Apart from the memory cost, we'd also need to
> keep track of 2kp+1 (mod 392863) as well as of 2kp+1 (mod 255255). If
> this takes more than 1/6th of the time to do the trial division, it's
> not worth it. (Actually it almost certainly _is_ worth it
Remember, adding more primes only seives out those with those new primes
as their *lowest* divisor. Thus adding the second seive table would eliminate
around 5%, not 15%.
In other words,
1-(2*4*6*10*12*16*18*22*28*30)/(3*5*7*13*17*11*19*23*29*31)!=(1-\
(2*4*6*10*12*16)/(3*5*7*13*17*11))+(1-(18*22*28*30)/(19*23*29*31))
So, it would have to be faster than 1/20th of the trial
division time, rather than 1/6th.
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
