- #71
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
- 14,983
- 28
Actually, I'm wrong -- you haven't quite gotten to the effectiveness of line sieving on 6n+1 and 6n-1: it appears you still want to allocate space for all numbers, but only work along those two lines.
It is more efficient to allocate only the space you intend to use. E.G., for sieving over 6n+1, you would:
Allocate an array T = [a, a+1, ..., b]
For each prime p:
Find the first number k in [a, b] such that 6k + 1 is divisible by p.
Cross off k, k + p, k + 2p, ... in T.
Go through the entries of T, and for each x that isn't crossed off, print 6x + 1.
Your "jump pattern" reduces to using the k you found when sieving 6n+1 to figure out the k you need when sieving 6n-1. (And yes, this idea is also already known -- e.g. look at optimizations of the multiple polynomial quadratic sieve)
It is more efficient to allocate only the space you intend to use. E.G., for sieving over 6n+1, you would:
Allocate an array T = [a, a+1, ..., b]
For each prime p:
Find the first number k in [a, b] such that 6k + 1 is divisible by p.
Cross off k, k + p, k + 2p, ... in T.
Go through the entries of T, and for each x that isn't crossed off, print 6x + 1.
Your "jump pattern" reduces to using the k you found when sieving 6n+1 to figure out the k you need when sieving 6n-1. (And yes, this idea is also already known -- e.g. look at optimizations of the multiple polynomial quadratic sieve)