# Can I use NextPrime[n] up to n=10^14?

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?

• 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 Dec 14, 2022 at 14:36
• 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?. Dec 14, 2022 at 16:31
• I wouldn't use NextPrime for such calculations, much more efficient method would involve simply PrimePi and Prime instead of NextPrime. Dec 14, 2022 at 16:41
• 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. Dec 15, 2022 at 8:10

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.

### 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"
];

• 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$). Dec 14, 2022 at 14:04

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}    *)
`