The naive prime test goes something like this:

  for(i=2; i<=sqrt(n); ++i):
     if n mod i == 0 :
       return false
  return true

If $n$ is prime the loop runs for $\sqrt(n)$ iterations. I was wondering what the "average" runtime is. It is of course troublesome to define this properly, because there is no uniform distribution on the natural numbers, so I don't know whether this question actually makes sense or not. My intuition is that "most" numbers have relatively small divisor and prime numbers are relatively rare.

Maybe the following definition works: Let $f(n)$ be the number of loop iterations necessary for testing the first $n$ numbers using the above function. What is a good upper bound for $f(n)/n$?


1 Answer 1


Better suitable for math.stackexchange.com.

It is quite widely known that about n / ln (n) numbers are primes, so you get $n^{1/2}$ iterations in about n / ln (n) cases.

You can try to figure out how often you have more than $n^{1/3}$ iterations: That happens if there is no prime factor less than $n^{1/3}$, and therefore the number is either prime or the product of two primes. So you either have a prime, and there are about n / ln n of those, or you have a product of two primes, that is a product of one prime p from $n^{1/3}$ to $n^{1/2}$, and one prime from p to n/p, and there only about (n/p) / ln (n/p) of those.

All other numbers take less than $n^{1/3}$ iterations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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