# reliable formulas/algorythms to find approximate number of primes up to a value and fast deterministic ways to check if a number is prime

I'm new to this place and I have two problems. I'm writing a program and I need to know:

(A) A formula/algorithm for the approximate number of prime numbers up to a number. Example: let's say that I wanted to know how many primes will show up from 0 to 100 and this formula would tell me it's 24 (in fact is 25 but I said 24 because I'm accepting a margin of error because considering the apparent randomness of prime numbers probably there isn't any formula yet that will give me the correct amount of primes at all times). If anyone knows of such formula/algorithm that has a maximum margin of error or a predictable margin of error please say so, I already found one but it was only for prime numbers that have a maximum distance of 2 between them and this won't cut it.

(B) A fast deterministic formula/algorithm to check if a number is prime, it may be for all prime numbers or just for Mersenne primes or any fast deterministic formula for determining if a number is some kind of prime or not, that you guys can remember.

P.S. I don't actually know a whole lot about math and it's pretty hard for me to understand some formulas, that's why i'm asking, please no 'uncommon' symbols (even if you have to substitute an 'uncommon' symbol by 10 simple operations/symbols it will be simpler for me), if it's not possible to someone to express something without using 'uncommon' symbols, express it step by step, by words. There's no point in giving a solution that the person that needs it can't understand.

• For the number of primes up to $x$, look for Prime Number Theorem in Wikipedia. For primality testing, again Wikipedia will give a good start. The fast deterministic tests are pretty sophisticated. Commented Nov 8, 2011 at 19:58
• We know your shift key isn't broken, because of your (A) and (B)... Still, better than all caps I suppose. Commented Nov 8, 2011 at 20:09
• @TonyK i don't want to be impolite with you. Commented Nov 8, 2011 at 20:21
• Is there a reason you want your test to be deterministic? Probabilistic tests are both faster and simpler, and can be repeated several times to make the probability of a false positive arbitrarily small. Commented Nov 8, 2011 at 20:23
• @André Nicolas i already saw that in wikipedia, the Prime Number Theorem won't cut it, if i try to extrapolate the number of primes from 0 to 1000 with it i will give me a number well bellow the reality because prime numbers get scarcer as we get along and the only value i would be working was the "possibility of primes in the vicinity of 1000" which is different from the "possibilty of primes in the vicinity of 50" unless you have a good tip to make this work it's useless to serve my purpose. Commented Nov 8, 2011 at 20:31

An estimate for the number of primes up to $n$ is $n/\log n$ (that's the natural logarithm, by the way). A better estimate is $n/(\log n-1)$. A better better estimate is $\int_2^n(1/\log t)\,dt$ but you have to know some Calculus to understand that one, and it takes some work to calculate it. It is believed that this last estimate makes an error of no more than roughly $\sqrt n\log n$, but to prove that you'd have to prove the Riemann Hypothesis. Which is hard.
• The error margin for $n/(\log n-1)$ is big-oh of $n/(\log n)^3$. Unfortunately, I can't find any explicit form of the constant implied by the big-oh. Here are some numbers: for $n=10,000,000$, the actual number is 664,579; $n/\log n$ gives 620,421; $n/(\log n-1)$ gives 661,459; the integral gives 664,918. Commented Nov 9, 2011 at 4:03
• The percentage error actually gets smaller as $n$ increases, so you only have to worry about very nearby points, not very distant ones. And 10% seems like a very generous error margin, I think you'll be fine with that. Commented Nov 10, 2011 at 0:20