View Single Post
Old 2006-07-22, 04:47   #17
Citrix's Avatar
Jun 2003

22·397 Posts


A quick question for you. If you consider 4*5^n+1. All n's left after sieving till 3 are multiples of 2 ie. all numbers left are x^2+1. Note that numbers of the form x^(2^y)+1 are generalized fermats and have factors of the form K*2^(Y+1)+1

So for 4*5^n+1 you only have to consider p=4*K+1. This makes sieving twice as fast compared to sieving for all primes.

I am currently working on 625. only numbers of the form 625*2^(4*n) are left. So all factors are of the form p=8K+1. I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.

Thank you in advance for the answer.
Citrix is offline   Reply With Quote