Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

Question

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time?

I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and $n/3$ calculations.

Answer 1

Calculating the primes up to $n$ in $O(n)$ time isn't particularly fast, and nor is it particularly slow. A naive Sieve of Eratosthenes works in time $O(n \log n \log \log n)$ and is very easy to implement. It can be sped up to run faster than $O(n)$ using some wheel techniques. I believe one can reduce the time to $O(n/\log n)$. See Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981) for more, or look up Pritchard's Wheel.

Another common algorithm is the Sieve of Atkin, which naively runs in $O(n)$, but which can also be sped up to sublinear time.

So no, it's not particularly interesting or special to come up with another algorithm to find the primes up to $n$ in time $O(n)$.

As an aside, you might read what allowed others to speed up the Sieve of Eratosthenes and the Sieve of Atkin to see if it would allow you to speed up your algorithm.