Marey's problem: Generating all prime numbers in $[n_1,n_2]$ - MathOverflow

Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T17:55:06Z

Is there are some references to algorithms that generate the set of prime numbers located between two given numbers n₁ and n₂?

I would like to consider the cases when n₁ is large while n₂-n₁ is small or while n₂-n₁ is large.

If we consider these cases:

[1] n₁=$2^{10}$ & n₂=$2^{11}$;

[2] n₁=$2^{40}$ & n₂=$2^{45}$, (modified to [2a]);

[3] n₁=$2^{100}$ & n₂=$2^{101}$, (modified to [3a]);

[4] n₁=$2^{1000}$ & n₂=$2^{1001}$, (modified to [4a]);

Is there is a well known algorithm to generate the set of all primes p ∈ [n₁,n₂] without generating all primes p < n₁?

By considering for example these cases:

[2a] n₁=$2^{40}$ & n₂=$2^{40}+2^{20}$;

[3a] n₁=$2^{100}$ & n₂=$2^{100}+2^{20}$;

[4a] n₁=$2^{1000}$ & n₂=$2^{1000}+2^{20}$.

Answer by Adeel for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:02:59Z

You can use prime sieves.

Answer by falagar for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:09:05Z

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 http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).

Answer by jp for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:20:22Z

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 Fermat test 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 Miller-Rabin tests to all candidates passing the Fermat test to reduce your error probability to a level you can tolerate (e.g., $2^{-100}).

Answer by BlueRaja for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:35:53Z

I'm assuming you're asking if we can generate primes in [n₁, n₂] without generating the primes before that (using a sieve), to which the answer is, no, nothing aside from testing every number between n₁ and n₂ for primality using something like Rabin-Miller.

Note that this will be significantly slower than sieving unless the numbers are extremely large and the range [n₁, n₂] is comparatively small.

Answer by Charles for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:47:45Z

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.

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.

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.

Answer by Bill Dubuque for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T21:12:45Z

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 thesis [1], 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, here [2] 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.

1 Wooding, Kjell. The Sieve Problem in One- and Two-Dimensions.
PhD Thesis. Calgary, Alberta. April, 2010

2 Lehmer, D.H. The sieve problem for all-purpose computers, MTAC, v. 7 1953, p. 6-14

Answer by TonyK for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-26T19:00:46Z

You can get away with storing $n_2^{1/4}$ bits for the sieving data. Generate the primes $<= 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]$.

Answer by Charles for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-27T00:35:11Z

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.

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.

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.

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.

Answer by François G. Dorais for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-27T18:53:17Z

The other answers have covered the right strategies, but here are a few additional comments.

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 & 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 2nd Mertens Theorem. 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 3rd Mertens Theorem. 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)$.

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.