View Single Post
Old 2007-07-08, 01:07   #47
Citrix's Avatar
Jun 2003

32×52×7 Posts

Another thing slowing up the sieve is that if gcd(x,max_prime)>1, then you would do 100's of additions just to for the factor, since it will never have a possible solution.

Extra additions for each factor=range_size*x/max_prime.

If max_prime=3 and x=720.

Then 240*2^23=2013265920 extra additions per factor.
So we should avoid these additions.

Last fiddled with by Citrix on 2007-07-09 at 00:51
Citrix is offline   Reply With Quote