5
$\begingroup$

I would like to perform computations with primes up to $n=10^{14}$. To do so, I would like to go through all primes, from $2$ to $10^{14}$ and perform some calculation on each prime.

I saw that one can use the NextPrime[] function to get the smallest prime greater than a given number. However, I find no information about how trustworthy this is, i.e., what I get is not a pseudo-prime, but a real, guaranteed prime number. Can I use it up to $10^{14}$ with confidence?

Also, are there any benchmarks on the speed of this function? How long would it take, for instance, on a modern processor to get up to $10^{14}$ with this?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ If you need to the all primes up to $10^14$, a segmented sieve would be the way to go. A rough implementation here: mathematica.stackexchange.com/a/85720/4346 $\endgroup$ Commented Dec 14, 2022 at 14:36
  • 2
    $\begingroup$ Currently all primes below $2^{63} - 1$ are calculated deterministically, $10^{18}<2^{63} - 1<10^{19}$. The same concerns NextPrime which works there quite well, however. finding e.g. tenth next prime is unsatisfactorily slow (NextPrime[10^19, 10]) See these posts: What is so special about Prime? and Why does iterating Prime in reverse order require much more time?. $\endgroup$ Commented Dec 14, 2022 at 16:31
  • 1
    $\begingroup$ I wouldn't use NextPrime for such calculations, much more efficient method would involve simply PrimePi and Prime instead of NextPrime. $\endgroup$ Commented Dec 14, 2022 at 16:41
  • 1
    $\begingroup$ To boost the signal of @GregHurst's comment: if one needs all the primes up to some point, one should always generate all those primes simultaneously—that's significantly faster than doing things one prime at a time. $\endgroup$ Commented Dec 15, 2022 at 8:10

2 Answers 2

Reset to default
9
$\begingroup$

NextPrime has no problems evaluating for large numbers well above $10^{14}$. I think it's safe to assume these are real prime numbers, for confirmation see the answer by @Roman (+1).

You can benchmark the performance of NextPrime and/or your analysis using AbsoluteTiming or RepeatedTiming for better statistics.

RepeatedTiming[ NextPrime[ RandomInteger[10^40] ] ,10 ] (* {0.00116824, 7254438951606515242301428266213800581027} *)

So after evaluating random large numbers repeatedly for 10 seconds, we get an average of 1.117ms per evaluation.

We expect that there will be approximately $n/Log(n)$ prime numbers smaller than $n$ (Prime number theorem), so assuming 1ms per iteration, your calculation will take more than 98 years.

With[ { n = 10^14 }, UnitConvert[ Quantity[1., "Millisecond"] * n/Log[n] ,"Years" ] ] (* Quantity[98.36705486320665, "Years"] *)

So unless your machine is much faster than mine and you have access to several hundreds of cores, even speeding things up via compilation, I think it may be hard to go over all prime numbers in the range $2$ to $10^{14}$ and do any meaningful tests on them.

enter image description here

Edit

After the excellent comment by @GregHurst code like the one below from here, could bring you down to a couple of weeks, without taking into account the time for your test. However, you may be limited by memory.

As pointed out by @Roman, we can know there are exactly PrimePi[10^14]$= 3204941750802$ prime numbers below $10^{14}$, and you better not try to have them all in memory (46 TB).

PrimesUpTo = Compile[{{n, _Integer}}, Block[{S = Range[2, n]}, Do[ If[S[[i]] != 0, Do[ S[[k]] = 0, {k, 2i+1, n-1, i+1} ] ], {i, Sqrt[n]} ]; Select[S, Positive] ], CompilationTarget -> "C", RuntimeOptions -> "Speed" ];
Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ You can get the exact number of primes less than $10^{14}$ with PrimePi[10^14], giving 3'204'941'750'802 (pretty close to your estimate of $n/\ln n$). $\endgroup$ Commented Dec 14, 2022 at 14:04
8
$\begingroup$

The prime generator and the primality proving package both seem very quick at $10^{14}$:

Needs["PrimalityProving`"] ProvablePrimeQ[NextPrime[10^14]] // AbsoluteTiming (* {0.004102, True} *)
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.