Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern Sieve of Atkin can do it in $O\left(\frac{n}{\log\log n}\right)$. (In both cases I assume that integer operations (sum, multiplication, modulo...) can be done in $O(1)$). My first question is:
Are asymptotically better algorithms currently known?
Now, concerning lower bounds on such an algorithm. Of course we need at least $\frac{n}{\log\,n}$ operations (because this is asymptotically the number of primes up to n). So:
Are there any reasons or heuristics that indicate whether an algorithm that does so in $O\left(\frac{n}{\log n}\right)$ should or should not exist?
Of course $O\left(\frac{n}{\log n}\right)$ should be really hard to achieve by traditional sieve methods, that usually involve writing down the numbers of a set asymptotically greater than the primes, and then sieving the non primes (I can't even think of an "easy to compute" set with size $O\left(\frac{n}{\log n}\right)$ that contains the primes). But can a more convincing heuristics or at least an absurd implication of the existence of such an algorithm be given?