[pycrypto] Distribution of prime numbers?

[Ximin Luo]

Dwayne C. Litzenberger wrote:
> On Sun, Oct 25, 2009 at 11:00:54PM -0400, Dwayne C. Litzenberger wrote:
>>     In other words: What is the a-priori probability of a number being 
>>     prime *before* we conduct any primality test?
> 
> Approximations, lower, or upper bounds are all useful.
> 
> I'm under the impression that the number of Rabin-Miller iterations needed  
> to establish that a certain number is probably prime depends on the answer 
> to this question.
> 

The precise formula is a millenium prize problem; see

http://en.wikipedia.org/wiki/Riemann_Hypothesis#Distribution_of_prime_numbers

You could probably get away with using some variant of

http://en.wikipedia.org/wiki/Prime_number_theorem#Statement_of_the_theorem

or

http://en.wikipedia.org/wiki/Prime_number_theorem#The_prime-counting_function_in_terms_of_the_logarithmic_integral

which is more accurate but more expensive to calculate (or so I'd imagine).

Both formulas gives the total number of primes smaller than a given number, so
you'd have to do some further tweaks to get the "a-priori probability of a
number being prime *before* we conduct any primality test?", such as dividing
by x or something.

X