0
$\begingroup$

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.

Thanks in advance.

  • 0
    @J. M. a fast deterministic method for any kind of prime will do it, for now i've concluded that pépin's test for fermat primes and lucas-lehmer test for mersenne primes seem to be the fastest deterministic methods to me, but it would be good to have some more input from people that really know the stuff, that's why i decided to make account on this place and ask (i already had 4 stack exchange accounts)2011-11-09

1 Answers 1

3

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.

  • 0
    @Gerry Myerson it makes sense getting smaller as it's asymptotic. somehow it fails with 10% at some points in the program so i made the margin 15% and it's working fine now. thank you very much for your help2011-11-10