Re: Prime Number Calculation
- To: mathgroup at smc.vnet.net
- Subject: [mg84670] Re: [mg84648] Prime Number Calculation
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 8 Jan 2008 06:45:50 -0500 (EST)
- References: <200801080630.BAA02151@smc.vnet.net>
On 8 Jan 2008, at 15:30, Jason Sidabras wrote: > Does anyone have any information about mathematica's prime number > algorithm (for Prime[x])? > > Do they use a sieve base algorithm or something more sophisticated? > > Thanks, > > Jason > The most likely method based on the function PrimePi. Of course one needs a good algorithm for computing PrimePi (without using a sieve) but there is one, originally due to Legendre and later greatly improved by others. Once you have got PrimePi, you can use FindRoot to invert it and you are essentially done. There are a few technical details to fill in but this is the basic idea and I am pretty sure it is very close to what Mathematica actually does. Andrzej Kozlowski
- References:
- Prime Number Calculation
- From: Jason Sidabras <jason.sidabras@gmail.com>
- Prime Number Calculation