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$?