DC's primes program

Could I just say that you're website is actually really cool. For that reason and also because youre smart im giving you a rep

What do you mean by linear time?

IIRC, using the standard sieve to find all the primes up to n takes time O(n log log n) so only barely slower than linear time.

There are more complex methods of finding $\pi(x)$ that can evaluate pi(n) in O(n^2/3) or even $O(n^{1/2 + \epsilon})$.

Note that these are all *exact* methods, not approximations.

My actual point is that when you say "this algorithm is linear", the missing information is "linear in what"?

For example, everyone got very excited when we found a primality testing algorithm of "polynomial complexity". But it's obvious that given a number n we can test if n is prime in O(n) time:

loop k from 2 to n
{
if (k divides n)
return "n is composite"
}
return "n is prime".

So, if we have a trivial linear test, why was polynomial complexity a big thing? Because the complexity is polynomial in the number of digits in n, which is a much bigger deal.

So here, you said it was linear, and my immediate reaction is "it's really not hard to find the number of primes < N in O(N) time". But it appears that what you actually meant (but never said) is "I can find (approximately) the number of primes < N^2 in O(N) time". Which is somewhat more interesting.

Having said that, however, I have to say that the approach you have taken is a fairly well travelled path. Nothing wrong with what you've done, but it's nothing earth shattering.