Thread: Idea for faster sieve View Single Post
2007-05-28, 02:58   #31
Citrix

Jun 2003

2·787 Posts

Quote:
 Originally Posted by geoff I speculated in another thread about modifying the Sieve of Eratosthenes so that it only sieved numbers of the form N*x+1 for some constant N, but I haven't found a way to do this efficiently, except when N is a power of 2.
There is an easy way, but requires 1 extra step for each prime in the low_primes array. You calculate N' (ie N inverse) mod p for every prime p in the array low_primes and store them in an array.

Then to sieve between start and stop. You find the first candidate where p divides the number ie. (start+x+1)%p=0. I assume that start and x are both divisible by N to make the example easier, though it is not needed.

1) then k*N+N*m+1==0 (mod p) where n*m=xand k*N=start
2) To find m we multiply both sides by N'
3) We get k+m+N'==0 (mod p)
4) Solve for m=-(k+N') (mod p)
5) Add p to m till you reach stop and cancel these values as primes.

If start is not a multiple of N, then you have to do an extra multiplication. But why not use start as a multiple of N and avoid the multiplication.

Hope this helps.