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?

$\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$
    – Greg Hurst
    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$
    – Artes
    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$
    – Artes
    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$ Dec 15, 2022 at 8:10

2 Answers 2

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"
];
$\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$
    – Roman
    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}    *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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