20101002, 14:14  #1 
Feb 2005
2^{2}×3^{2}×7 Posts 
sieving primes in arithmetic progressions
Does there exist a fast optimized siever for finding primes in a given arithmetic progression?
That is, for given the parameters A, B along with the range [L,U], such siever should find and report all primes of the form A*k + B in the interval [L,U]. It is not a big deal to write my own siever (based on ala sieve of Eratosthenes or Atkin) but I'd rather use a fast existing siever if there is such a beast. Last fiddled with by maxal on 20101002 at 14:15 
20101002, 14:58  #2 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
well to get the candidates just find k such that A*k+B are on the lines 6n+1 or 6n1.

20101002, 16:23  #3 
Jan 2005
Caught in a sieve
5×79 Posts 
Hm, that kinda looks like k*2^n+1, doesn't it? I may know something about this.
Let's see...you want to find: k*A+B = 0 (mod P) k*A = B (mod P) k = B*A^1 (mod P) Now, B (mod P) is just PB, assuming B < P. A^1, on the other hand, is a Modular multiplicative inverse. Those take a little more work, but they can be worth it. Especially if A is of a special form that makes it easy. 
20101002, 16:40  #4 
Feb 2005
374_{8} Posts 
I'm not asking about the theory, I'm asking about the _software_.

20101002, 16:43  #5 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 

20101002, 16:44  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 

20101002, 17:23  #7 
Feb 2005
2^{2}×3^{2}×7 Posts 
science_man_88, I asked concrete question about the software  if you don't know the answer, please don't make irrelevant comments.
And please don't teach me the theory  believe me, I know it well. 
20101002, 17:41  #8 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
look if you want a siever either build one if you can or look as apparently nothing else is what you want so why post it here.

20101003, 13:44  #9 
A Sunny Moo
Aug 2007
USA (GMT5)
14151_{8} Posts 
PrimeGrid did a big search for an AP26 earlier this year; I'm not sure how they went about doing it, but I would assume that a fast sieve was part of it somewhere along the way. You might try asking in their AP26 subproject forum about it.

20101003, 17:13  #10 
Feb 2005
2^{2}×3^{2}×7 Posts 
AP26 is irrelevant. I'm not looking for primes forming an arithmetic progression, but primes in the given arithmetic progression (possibly with gaps between them). The latter problem is much simpler than the former one.

20101003, 17:32  #11 
Jun 2003
2·3^{2}·269 Posts 
yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Arithmetic progressions for n  MattcAnderson  MattcAnderson  28  20170508 20:58 
Compositions of arithmetic progressions  jasonp  Factoring  8  20110820 13:42 
Sieving for primes  CRGreathouse  Math  0  20090106 14:38 
Detecting arithmetic progressions  grandpascorpion  Math  18  20070328 15:08 
Arithmetic and Polynomial Progression of Primes?  drake2  Math  13  20061010 00:43 