Mc Laughlin, James on Wed, 16 Mar 2005 19:52:44 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

RE: *** prime: not enough precomputed primes


Thanks. That helps somewhat. 
 
This could be an area for future development for pari/gp, since when I input to Mathematica, I get back what I want (although it does take a couple of minute):
 
Prime[10^12]

29996224275833

In other words, it should be possible to build a program in pari that will output the 10^12th prime.

Jimmy Mc Laughlin.



________________________________

From: Karim Belabas [mailto:Karim.Belabas@math.u-psud.fr]
Sent: Wed 3/16/2005 3:24 AM
To: pari-users@list.cr.yp.to
Subject: Re: *** prime: not enough precomputed primes



* Mc Laughlin, James [2005-03-16 07:48]:
> (01:38) gp > prime(10^7)
>
>   *** prime: not enough precomputed primes
> 
> How do get a larger list of precomputed primes so that, for example,
> prime(10^12)
> will return the 10^12th prime?

The answer to the first part of the question is

  default(primelimit, 100M) [ or 100000000, or 10^8 ]

[ you may also edit the gprc file to make it the default; or, starting gp from
a shell, you can type gp -p 100M ] 

The answer to the second part is: you can't. Functions dealing with prime
numbers (prime, primes, primepi, forprime...) are implemented with a (very)
naïve algorithm, requiring all needed primes to be precomputed. No
on-the-fly sieving.

So, to get the 10^12-th prime, you need to store all primes up to
~ 10^12 log(10^12) ~ 2.8 E13. And it's doubtful your hardware will be up
to the task [ gp won't even let you try on a 32-bit architecture. Then
you'll need a few TBytes of main memory. ].

Sorry,

    Karim.
--
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]