Marey's problem: Generating all prime numbers in $[n_1,n_2]$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:02:24Z http://mathoverflow.net/feeds/question/33304 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2 Marey's problem: Generating all prime numbers in $[n_1,n_2]$ Mohammed Marey 2010-07-25T17:55:06Z 2010-07-29T10:44:58Z <p>Is there are some references to algorithms that generate the set of prime numbers located between two given numbers n<sub>1</sub> and n<sub>2</sub>?</p> <p>I would like to consider the cases when n<sub>1</sub> is large while n<sub>2</sub>-n<sub>1</sub> is small or while n<sub>2</sub>-n<sub>1</sub> is large.</p> <p>If we consider these cases: </p> <p>[1] n<sub>1</sub>=$2^{10}$ &amp; n<sub>2</sub>=$2^{11}$; </p> <p>[2] n<sub>1</sub>=$2^{40}$ &amp; n<sub>2</sub>=$2^{45}$, (modified to [2a]);</p> <p>[3] n<sub>1</sub>=$2^{100}$ &amp; n<sub>2</sub>=$2^{101}$, (modified to [3a]);</p> <p>[4] n<sub>1</sub>=$2^{1000}$ &amp; n<sub>2</sub>=$2^{1001}$, (modified to [4a]);</p> <p>Is there is a well known algorithm to generate the set of all primes p &isin; [n<sub>1</sub>,n<sub>2</sub>] without generating all primes p &lt; n<sub>1</sub>?</p> <p>By considering for example these cases:</p> <p>[2a] n<sub>1</sub>=$2^{40}$ &amp; n<sub>2</sub>=$2^{40}+2^{20}$;</p> <p>[3a] n<sub>1</sub>=$2^{100}$ &amp; n<sub>2</sub>=$2^{100}+2^{20}$; </p> <p>[4a] n<sub>1</sub>=$2^{1000}$ &amp; n<sub>2</sub>=$2^{1000}+2^{20}$. </p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33306#33306 Answer by Adeel for Marey's problem: Generating all prime numbers in $[n_1,n_2]$ Adeel 2010-07-25T18:02:59Z 2010-07-25T18:02:59Z <p>You can use <a href="http://en.wikipedia.org/wiki/Generating_primes#Prime_sieves" rel="nofollow">prime sieves</a>.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33307#33307 Answer by falagar for Marey's problem: Generating all prime numbers in $[n_1,n_2]$ falagar 2010-07-25T18:09:05Z 2010-07-25T18:09:05Z <p>If $n_1$ and $n_2$ are not too big you can use Eratosthenes sieve (see wikipedia for this). If they are big enought you can use sieve to cross out numbers which have small prime divisors and after that check every number that wasn't crossed out and check if it is prime using any primality test (see <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow">http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test</a>).</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33308#33308 Answer by jp for Marey's problem: Generating all prime numbers in $[n_1,n_2]$ jp 2010-07-25T18:20:22Z 2010-07-25T20:34:03Z <p>The fastest approach should be first to sieve the numbers by marking the numbers divisible by small primes (for this you should use only one long division per short prime), then to use a <a href="http://en.wikipedia.org/wiki/Fermat_primality_test" rel="nofollow">Fermat test</a> to the base 2 (as it is more efficient since multiplication with 2 is a left shift) on all unmarked numbers. Finally apply a certain number of <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow">Miller-Rabin tests</a> to all candidates passing the Fermat test to reduce your error probability to a level you can tolerate (e.g., $2^{-100}).</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33310#33310 Answer by BlueRaja for Marey's problem: Generating all prime numbers in$[n_1,n_2]$BlueRaja 2010-07-25T18:35:53Z 2010-07-25T18:35:53Z <p>I'm assuming you're asking if we can generate primes in [n<sub>1</sub>, n<sub>2</sub>] without generating the primes before that (using a sieve), to which the answer is, no, nothing aside from testing every number between n<sub>1</sub> and n<sub>2</sub> for primality using something like <a href="http://en.wikipedia.org/wiki/Rabin-Miller" rel="nofollow">Rabin-Miller</a>.</p> <p>Note that this will be significantly slower than sieving unless the numbers are extremely large and the range [n<sub>1</sub>, n<sub>2</sub>] is comparatively small.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33311#33311 Answer by Charles for Marey's problem: Generating all prime numbers in$[n_1,n_2]$Charles 2010-07-25T18:47:45Z 2010-07-26T17:07:41Z <p>Let$S=\sqrt{n_2}$. If S is bigger than your computer's memory in bits, then you're going to have trouble generating all the primes in that range; if you insist, break the range into pieces that fit into memory, mark off the ones with small divisors, and test the remaining numbers for primality. You want to do as much sieving as possible, so fill maybe half the memory with primes and use those for sieving.</p> <p>If S fits in memory and$n_2-n_1$is not much smaller than S, use a sieve (sieve of Atkin or Eratosthenes). You may need to use a segmented version of the sieve, depending on how large$n_2-n_1$is.</p> <p>If$n_2-n_1$is significantly smaller than S, make a bit array of (segments of?) the range, mark off small divisors, and test the remaining members for primality.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33324#33324 Answer by Bill Dubuque for Marey's problem: Generating all prime numbers in$[n_1,n_2]$Bill Dubuque 2010-07-25T21:12:45Z 2010-07-25T21:12:45Z <p>Unless you have very specialized needs, you can probably apply standard sieving techniques. Here are a couple references. First, hot off the press is Kjell Wooding's Calgary <a href="http://math.ucalgary.ca/~hwilliam/files/wooding10thesis.pdf" rel="nofollow">thesis [1]</a>, which includes a good overview of both software and hardware sieving techniques (e.g. FPGA-based sieves, Calgary's scalable sieve, etc). Its bibliography should prove useful as an entry point into the literature. Also, <a href="http://www.ams.org/journals/mcom/1953-07-041/S0025-5718-1953-0052876-7/S0025-5718-1953-0052876-7.pdf" rel="nofollow">here [2]</a> is a charming classic paper by D.H. Lehmer - one of the pioneers of computational number theory. It gives a nice succinct introduction to sieving in general. Such methods have a long venerable history that stimulated much development in both number theory and computer science, e.g. google "Lehmer sieve" and you'll discover many ingenious machines devised to carry out number theoretical computations long before the dawn of the modern digital computer, e.g. via bicycles chains, photoelectric devices, etc.</p> <p><a href="http://math.ucalgary.ca/~hwilliam/files/wooding10thesis.pdf" rel="nofollow">1</a> Wooding, Kjell. The Sieve Problem in One- and Two-Dimensions.<br> PhD Thesis. Calgary, Alberta. April, 2010</p> <p><a href="http://www.ams.org/journals/mcom/1953-07-041/S0025-5718-1953-0052876-7/S0025-5718-1953-0052876-7.pdf" rel="nofollow">2</a> Lehmer, D.H. The sieve problem for all-purpose computers, MTAC, v. 7 1953, p. 6-14</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33430#33430 Answer by TonyK for Marey's problem: Generating all prime numbers in$[n_1,n_2]$TonyK 2010-07-26T19:00:46Z 2010-07-26T19:08:41Z <p>You can get away with storing$n_2^{1/4}$bits for the sieving data. Generate the primes$&lt;= n_2^{1/4}$, and use them to generate the primes in successive intervals of length$n_2^{1/4}$dynamically, up to$n_2^{1/2}$. The primes thus generated can be used to generate the primes in the interval$[n_1,n_2]$.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33458#33458 Answer by Charles for Marey's problem: Generating all prime numbers in$[n_1,n_2]$Charles 2010-07-27T00:35:11Z 2010-07-27T00:35:11Z <p>This was originally a comment on TonyK's answer, but it was too large to submit as a comment so I'm putting it here. I thought the numbers might have value to some.</p> <p>Let's say that it takes$b^{\lg 6}/10^{10}$seconds to test a$b$-bit number with the M-R test and$b^{\lg 24}/10^{13}$seconds to prove primality with ECPP. Testing a range up to$n_2=2^b$with M-R + ECPP would take about $$\left(n_2-n_1\right)\left(\frac{b^{\lg 6}}{10^{10}}+\frac{b^{\lg 24}}{10^{13}\ln n_2}\right)=\left(n_2-n_1\right)\left(\frac{b^{\lg 6}}{10^{10}}+\frac{b^{\lg 12}}{10^{13}\ln2}\right)$$ seconds. For$n_2-n_1=2^{20}$and$n_2$large, this is about$1.5(\lg n_2)^{\lg12}/10^7$seconds.</p> <p>On the other hand, suppose sieving$n_1$to$n_2$takes$\sqrt{n_2}/10^6+(n_2-n_1)/10^{8.5}$seconds. For$n_2-n_1=2^{20}$and$n_2$large, this is about$\sqrt{n_2}$seconds.</p> <p>Equating the two suggests that, for intervals about a million wide, testing each member is superior to sieving beyond about$n_2>8\cdot10^8$. Only about 12 kB of memory are needed to store all the primes up to the square root of that limit, so the fourth power trick doesn't seem viable here at all -- by the time you run out of primary memory you shouldn't be sieving at all.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33554#33554 Answer by François G. Dorais for Marey's problem: Generating all prime numbers in$[n_1,n_2]$François G. Dorais 2010-07-27T18:53:17Z 2010-07-27T22:15:38Z <p>The other answers have covered the right strategies, but here are a few additional comments.</p> <p>On an idealized computer with an unbounded amount of memory, the cost of sieving$[n_1,n_2]$for the prime$p$is$C_1(n_2-n_1)/p$for some constant$C_1$, the average cost of a memory read &amp; write operation. Therefore, the cost of sieving$[n_1,n_2]$for all primes up to some bound$B$is $$C_1 (n_2 - n_1) \sum_{p\leq B} \frac{1}{p} = (n_2 - n_1) (C_1 \log \log B + O(1)),$$ by the <a href="http://en.wikipedia.org/wiki/Mertens%27_theorems" rel="nofollow">2nd Mertens Theorem</a>. The numbers in$[n_1,n_2]$that remain after sieving is approximately $$(n_2-n_1)\prod_{p \leq B} \left(1-\frac{1}{p}\right) = (n_2 - n_1) \frac{e^{-\gamma}}{\log B},$$ by the <a href="http://en.wikipedia.org/wiki/Mertens%27_theorems" rel="nofollow">3rd Mertens Theorem</a>. Therefore, the time for testing the remaining numbers for primality is about $$C_2(n_2-n_1) \frac{e^{-\gamma}}{\log B},$$ where$C_2$is the average cost of a single primality test. The optimal sieving bound$B$is then approximately$\exp(e^{-\gamma} C_2/C_1)$.</p> <p>The "constants"$C_1$and$C_2$are best determined empirically. In reality, the constant$C_1$depends heavily on the length of the interval$[n_1,n_2]$while the constant$C_2$depends mostly on the size of$n_2$. The constant$C_2$should vary smoothly with$n_2$, but there will be sharp increases in$C_1$when the cache size is exceeded and a still larger increase if disk swaps are necessary. Here is a trick that will help you fit longer intervals into the cache, especially if you have multiple processors available. The cost of sieving is higher for small primes, to save some of this time, break the interval into arithmetic progressions$a + Mx$, where$\gcd(a,M) = 1$and$M = 2\cdot 3 \cdots p_i$is the product of the first$i$primes. Each such progression can be sieved independently, possibly on different processors. Essentially, we're breaking the interval into$\phi(M) = (2-1)(3-1)\cdots(p_i-1)$different progressions which each require$(n_2-n_1)/M$bits to store in memory while the total sieving and testing times remains about the same. I have some C code that implements this strategy with$M = 2\cdot 3 \cdots 29\$ if you're interested.</p>