1
$\begingroup$

Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M is at most $2\times10^7$. I know that the sieve of Eratosthenes method works in $O(n\log\log n)$ time, but it would require calculating the number of primes up to $M$, which goes up to $10^{10}$ so it would be too slow.

$\endgroup$
4
  • 1
    $\begingroup$ consider the special case where N == M-1 $\endgroup$ – John Dvorak Apr 1 '20 at 14:49
  • $\begingroup$ Only requires primes up to sqrt(M). Otherwise the whole sieve idea would be a bit daft, and Eratosthenes surely wouldn’t have lent its name to it. $\endgroup$ – gnasher729 Apr 1 '20 at 15:29
  • 1
    $\begingroup$ Linear in what? Linear in $M-N$? Are you OK with $O((M-N) \log M)$ or $O((M-N) \text{poly}(\log M))$? $\endgroup$ – D.W. Apr 1 '20 at 16:12
  • $\begingroup$ Linear to M-N, so 𝑂((𝑀−𝑁)log𝑀) or 𝑂((𝑀−𝑁)poly(log𝑀)) would suffice. $\endgroup$ – pblpbl Apr 1 '20 at 17:43
2
$\begingroup$

Using the Sieve of Eratosthenes this takes $O((M-N) + M^{1/2}) \log \log M)$. This will be the fastest unless M is quite large and / or N is quite close to M.

If you had a case like $M = 10^{100}$, $N = 10^{100} - 10^{10}$ you would likely start with a sieve to throw out all of the 10 billion candidates that have a small divisor, leaving you with say $10^9$ candidates. Then you'd use Fermat's primality test to find all probable primes. Then you'd either say "that's good enough", or you follow it by a deterministic primality test for the remaining 43.4 million or so probable primes.

If you do a deterministic primality test then you would run Fermat's test with fewer individual tests since you don't mind a few "probable primes" that are composite. If you don't do a deterministic primality test then you would run Fermat's test for a bit longer. In practice the question would be: What is the chance that there is a "probable prime" that is really composite, vs. what is the chance that a number is reported incorrectly as prime / non-prime because of a hardware problem.

$\endgroup$
2
  • $\begingroup$ There are a number of cases where using a fast prime count method (e.g. LMO or its extensions) for the two endpoints can be faster. In practice it depends hugely on the implementations of each method. The numbers here (up to 10^10 with windows 10^7 or smaller) are often in the threshold where the two compete. E.g. 10^10 to 10^10+10^9 is almost certainly going to favor the prime count method. A tiny window will favor the sieve. You are spot on with the bigint window -- we want to do a partial sieve followed by BPSW. Let the user decide if they really want a proof for each probable prime. $\endgroup$ – DanaJ Jul 15 '20 at 2:52
  • $\begingroup$ Minor comment: it isn't just hardware, but software problems that can enter in. You can wait 10 years for AKS to finish, then find out they misread the logarithm base in the paper (very common mistake) so it isn't really proved after all. At least with ECPP you get a certificate so both the prover and any verifiers would have to be broken in the same way. Another minor aside is that that Miller-Rabin takes essentially identical time to a Fermat test and has some advantages, and furthermore since base-2 MR is half the BPSW test... $\endgroup$ – DanaJ Jul 15 '20 at 2:58
0
$\begingroup$

You possibly cannot do it in time linear to $M-N$. Suppose to the contrary there is such algorithm that runs in $C(M-N)$ time for $M-N\ge K$, then for any large enough integer $n$, we can use this algorithm to count the number of primes in $[n-K,n)$ and $[n-K,n+1)$ to check whether $n$ is a prime, in $CK+C(K+1)$ time. Note this time is independent of $n$, so we can now check whether $n$ is a prime in constant time for sufficient large $n$, which is possibly impossible.

$\endgroup$
4
  • $\begingroup$ Big-O doesn't care about small values. You only need c (M-N) steps if M-N is large, not when M-N = 1. $\endgroup$ – gnasher729 Apr 2 '20 at 9:17
  • $\begingroup$ @gnasher729 Does it make sense now? $\endgroup$ – xskxzr Apr 2 '20 at 10:18
  • $\begingroup$ OP allows polylog factors that depend on $M$ or $N$ separately. $\endgroup$ – Dmitri Urbanowicz Apr 2 '20 at 11:05
  • $\begingroup$ @DmitriUrbanowiczD That does not mean linear to $M-N$... I'll leave the answer so that others reading this post may get help. $\endgroup$ – xskxzr Apr 2 '20 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.