Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Prime Number Calculation

• To: mathgroup at smc.vnet.net
• Subject: [mg84687] Re: Prime Number Calculation
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Thu, 10 Jan 2008 02:22:41 -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>