[Date Index] [Thread Index] [Author Index]

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/