Average runtime of naive primality test

Question

The naive prime test goes something like this:

is_prime(n):
  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$?

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.