MathGroup Archive 2008

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

Search the Archive

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


  • Prev by Date: Re: Using MathLink with Visual Express
  • Next by Date: Re: nontrivial solution of Euler-beam problem?
  • Previous by thread: Prime Number Calculation
  • Next by thread: Re: Prime Number Calculation