Percent chance of being prime

[xilman]

Originally Posted by henryzz

how without counting the primes can i work this out

i want to use this for hopefully having p and q being 100 digit primes
how long do u think ( pi(p^2) - pi(q^2) )/ (p^2 - q^2 ) would take if p and q are 100 digit primes

is there a quick way

Yes, there is a quick way. You use Google to find sites which explain how to calculate pi(x), either exactly or to an adequate approximation, and then plug in the numbers you want to use.

Please stop expecting people to do work for you that you can do for yourself very easily, and with less effort all round.

As several posters have said before, you'll find people here very willing to help you if you've made an honest attempt to solve your problems but then get stuck. If you don't show you've made such an attempt, those people will either become hostile or will ignore you completely --- on this occasion and when you ask for help later.


Paul

[henryzz]

sorry i hadnt heard of pi(x) and for soom reason i didnt think of googling it

[akruppa]

If you are seriously interested in learning about number theory and primes in particular, the book by Crandall and Pomerance: Prime Numbers would make an excellent starting point. The prime counting function and approximations to it are among the many things explained in it.

Alex

[ATH]

http://mathworld.wolfram.com/PrimeNumberTheorem.html

You can estimate pi(n) by:

0.922*n/ln(n) < pi(n) < 1.105*n/ln(n)

[R.D. Silverman]

Originally Posted by ATH

http://mathworld.wolfram.com/PrimeNumberTheorem.html

You can estimate pi(n) by:

0.922*n/ln(n) < pi(n) < 1.105*n/ln(n)

This is much too crude an estimate. Much better estimates are
available.

Look up "Rosser & Schoenfeld" and "Robin"

[xilman]

Originally Posted by R.D. Silverman

This is much too crude an estimate. Much better estimates are available.

Look up "Rosser & Schoenfeld" and "Robin"

Crudity depends on circumstances.

When, for example, I want to estimate how many relations will be needed to complete a NFS factorization I us 0.8*(pi(LPB1) + pi(LPB2). That estimate is so crude, and yet sufficiently accurate for the purpose, that approximating pi(x) as x/(ln(x)-1) is easily adequate and very simple to calculate.

(LPB1 and LPB2 are the Large Prime Bounds on the algebraic and rational sides, though not necessarily in that order.)

Paul