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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ consider the special case where N == M-1 $\endgroup$– John DvorakApr 1, 2020 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$– gnasher729Apr 1, 2020 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, 2020 at 16:12
-
$\begingroup$ Linear to M-N, so ๐((๐โ๐)log๐) or ๐((๐โ๐)poly(log๐)) would suffice. $\endgroup$– pblpblApr 1, 2020 at 17:43
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
-
$\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$– DanaJJul 15, 2020 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$– DanaJJul 15, 2020 at 2:58
-
$\begingroup$ @DanaJ: Practically, there is the question: Is a number that your algorithm called a "probable prime" really composite because you didn't run the test long enough, or because of a hardware failure? Because if a hardware failure is more likely, then being a "proven prime" by your algorithm doesn't mean it's prime :-( $\endgroup$ Nov 1, 2022 at 10:27
-
$\begingroup$ @DanaJ I think for Fermat primes, almost half of the Fermat numbers tested have a proof that they are composite in the form of a small factor, and for the other half we have nothing. If I didn't trust a table of Fermat primes, I'd basically have to redo about half the work. $\endgroup$ Nov 1, 2022 at 10:29
-
$\begingroup$ If one has a certificate, it can be verified "rapidly" (compared to the proof time) by independent software/hardware. But we're probably off in the weeds -- using BPSW or some random-base Miller-Rabin tests is good enough for most practical uses. I think your general point is solid. $\endgroup$– DanaJNov 2, 2022 at 12:26
$\begingroup$
$\endgroup$
4
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.
-
$\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$ Apr 2, 2020 at 9:17
-
-
$\begingroup$ OP allows polylog factors that depend on $M$ or $N$ separately. $\endgroup$ Apr 2, 2020 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$– xskxzrApr 2, 2020 at 12:30