How is Prime[n] implemented in Mathematica? I have just observed that calculating large primes is quite fast (but not in O(1) time).

In[9]:= Prime[10^11]                                                       
Out[9]= 2760727302517 //not instant
In[10]:= Prime[10^11]                                                      
Out[10]= 2760727302517 //instant
In[11]:= Prime[10^12]                                                      
Out[11]= 29996224275833 //not instant, seems to be k times longer than 10^11

I have also observed that it uses ~O(1) memory so things like Atkin sieve are not used there and that results are stored in memory because each next query returns result instantly.

In reference there are not details about that.

From the other hand it can't be predefined (it is not O(1)) but after putting:

In[13]:= Prime[10^20]                                                      

Prime::largp: Argument 100000000000000000000 in 
    Prime[100000000000000000000] is too large for this implementation.

Out[13]= Prime[100000000000000000000]

Why is this bound if that implementation has not predefined primes?

  • 4
    $\begingroup$ From Some Notes on Internal Implementation: "Prime and PrimePi use sparse caching and sieving. For large $n$, the Lagarias–Miller–Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime." $\endgroup$
    – MarcoB
    Dec 18, 2019 at 18:43
  • $\begingroup$ Interesting source @MarcoB $\endgroup$
    – mvxxx
    Dec 18, 2019 at 18:47
  • 1
    $\begingroup$ Basically this question has been asked in What is so special about Prime?. There is an arbitrary cut-off for PrimePi and then "inverting" it we get a bound for Prime. $\endgroup$
    – Artes
    Dec 18, 2019 at 19:28