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.