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
    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.2011-11-08
  • 0
    We know your shift key isn't broken, because of your (A) and (B)... Still, better than all caps I suppose.2011-11-08
  • 0
    @TonyK i don't want to be impolite with you.2011-11-08
  • 0
    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.2011-11-08
  • 0
    @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.2011-11-08
  • 0
    @André Nicolas i saw the page about primality testing too and for fast deterministic methods wikipedia is far from having a good deal of information. i already made programs with a slow deterministic method (a highly optimized trial division algorithm that i came up with), fast deterministic methods may be complex but everything that is complex has a simple explanation so if you know well any of it, just hit me ;)2011-11-08
  • 0
    @user7530 well because it's impossible to know if a number is really prime if i don't use a deterministic test, for this program i need accuracy in favor of speed, but i also need some speed (i mean i won't do trial division for numbers in the vicinity of 1.000.000.000.000.000 and above, that would be suicidal)2011-11-08
  • 0
    Speaking somewhat loosely, the probability that a randomly chosen integer near $n$ is prime is roughly $\frac{1}{\log n}$ where $\log$ is the "natural" (base $e$) logarithm. One can do better a better count than $\frac{n}{\log n}$ by using the "logarithmic integral."2011-11-08
  • 0
    There is [this](http://math.stackexchange.com/questions/5277), and [this](http://math.stackexchange.com/questions/939). Now, which one is the duplicate...2011-11-09
  • 0
    @J. M. the second link has nothing to do with my question as i already knew how to calculate if a number is prime, and i want fast deterministic ways of doing it ONLY. the first link sure seems to be the same thing as my first question when i further investigated (by this i mean i could not understand how PI(x) could be related as i didn't had a clue what i asked was the same, and i don't have to), besides that, the answer here was better so sew me. p.s. i check like 10 questions before posting my own, this isn't my first rodeo on questions and answers so go torment supposed new guys elsewhere2011-11-09
  • 0
    I'm not sure which part of my comment was "tormenting" (and I don't know how you can guess what my intent was as you don't know jack about me, either); I am pointing out other threads of relevance, and I am wondering whether any of those are probable dupes. I never make assumptions on "newness" of a member or anything. Now to the math: you definitely need to tangle with the prime counting function. Gerry's answer alludes to $\pi(n)$, in fact. It is now entirely up to you whether you should pursue the pieces I left you or not. Have a good one, sir.2011-11-09
  • 0
    @J. M. i always feel a little sickened by those that assume that 'the new guy needs to be taught to search other posts and i will grab some very look-alike questions here and there and throw them at it'. there are a lot of guys that are trolls and, quoting "Now, which one is the duplicate..." is certainly implying that one is, and i'm sure you can tell the difference between them to understand that they aren't. now if what i'm saying wasn't your intention, i am very sorry for what i said to you. but i'm sure that if you continue saying stuff that way, much more misunderstandings might happen2011-11-09
  • 0
    Well, it is hard to search for mathematical expressions, and it is even harder to search for something you don't know the name of. Hence the links. If you profit from following those leads, all well and good; if not, a simple "Thank you, but those don't look relevant for me because..." would have sufficed. FWIW: I managed to pull those links because I *know* those questions, and I thus did not have to search.2011-11-09
  • 0
    FWIW: yes, Miller-Rabin can be modified to be deterministic, but it is not that practical (yet). AKS has yet to be made practical, even in its probabilistic versions. I don't think I've ever seen a deterministic method that is at least as good (in terms of efficiency) as a probabilistic method. At the very least, combining Miller-Rabin with a Lucas pseudoprime test makes for a (seemingly) reliable primality tester. (Of course, if your primes have special structure, one can do better; you do need to specify which special primes you had in mind, as the question is otherwise too broad.)2011-11-09
  • 0
    For $\pi(n)$: you'll want to look up stuff by Andrew Odlyzko. Gerry's logarithmic integral estimate is quite good, and one can polish that estimate by using Odlyzko's methods.2011-11-09
  • 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