Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  André Nicolas Nov 8 '11 at 19:58
    
We know your shift key isn't broken, because of your (A) and (B)... Still, better than all caps I suppose. –  TonyK Nov 8 '11 at 20:09
    
@TonyK i don't want to be impolite with you. –  wxiiir Nov 8 '11 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. –  user7530 Nov 8 '11 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. –  wxiiir Nov 8 '11 at 20:31
show 11 more comments

1 Answer

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.

share|improve this answer
    
good answer for my first question, very complete. i will see if i can understand something about the 'better better estimate', if not i will fall back to the other options. –  wxiiir Nov 8 '11 at 22:44
    
sorry about asking but do you know anything about the error margin of n/(log n−1)? i cant find it anywhere and assigning a random error margin goes a bit against my programmer instincts. –  wxiiir Nov 9 '11 at 1:39
    
+1 for the last sentence. –  Brandon Carter Nov 9 '11 at 1:44
1  
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. –  Gerry Myerson Nov 9 '11 at 4:03
1  
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. –  Gerry Myerson Nov 10 '11 at 0:20
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.