Re: Primes (again)

*To*: mathgroup at smc.vnet.net*Subject*: [mg53034] Re: [mg53024] Primes (again)*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Tue, 21 Dec 2004 05:19:09 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

On 20 Dec 2004, at 20:34, George Szpiro wrote: > this is probably a naive question, but how does Mathematica give the > result of > Prime[k]? Since the numbers are not stored anywhere, and there is no > algorithm to "compute" them, how does Mathematica produce them? > > Thanks to everybody, especially to Dr Bob and Yehuda Ben-Shimol, for > answering my previous questions. > > Best regards, > George > > -- > > -------- > George Szpiro > Neue Z=FCrcher Zeitung (Switzerland) > POB 6278 > Jerusalem 91060 > Israel It uses the function PrimePi and some numerical root finding method like FindRoot. (It is very easy to write such a function yourself). Thus the computation reduces to having a reasonably fast algorithm for PrimePi. There is such an algorithm due to Legendre (using Legendre Sum). All this can be found in most texts on number theory. A good place to look is Bressoud and Wagon "A Course Computational Number Theory" which is Mathematica based. Andrzej Kozlowski Chiba, Japan http://www.akikoz.net/~andrzej/ http://www.mimuw.edu.pl/~akoz/