Yes, the harder version is also possible.

The basic method is to never construct the full sieve, but only the portions of it that cannot be easily filtered out in advance.

Consider the state of the sieve after filtering out the first few primes.
For example, suppose that we have already filtered out 2, 3 and 5. The sieve
now contains all numbers whose smallest prime factor is greater than 5. Consider
the state of the sieve as a function, *S*_{5}, where
*S*_{5}(*x*) is 0 if *x* is not in the sieve (it
has a divisor that is at most 5) and 1 otherwise. This function is periodic,
with a cycle of length 2×3×5=30.

Instead of creating the entire sieve up to *n*, we can therefore compute
only the first 30 elements in the sieve. All other elements can be viewed as
repetitions of the same.

Looking at the sieve in this state, we see that the next prime is 7. In order
to update the sieve, we merely need to extend the 30-length sieve 7 times until
it reaches length 210 (or until it reaches length *n*, if *n*<210),
and then employ the fast method of Euler's sieve in order to filter out all
elements divisible by 7.

How much is saved by pruning the sieve as it is built up, rather than as a last step?

Let us name the primes *p*_{1}, *p*_{2},...
At the *k*'th step, the sieve expands from a length of
*p*_{1}×...×*p*_{k-1}
to a length of
*p*_{1}×...×*p*_{k}.
As it starts, it has
(*p*_{1}-1)×...×(*p*_{k-1}-1)
elements, as this is the number of elements in the range that do not divide
any of the first *k*-1 primes. The algorithm then creates a sieve with
*p*_{k} times as many elements, and removes from these
as many as there were in the sieve to begin with, for a total multiplicative
expansion by a factor of *p*_{k}-1 in the number of
remaining elements.

Let *r*=ceil(*n*/(*p*_{1}×...×*p*_{k-1})).

If *k* is the last step to be performed, then *r*≤*p*_{k}. Let us switch to a slightly less efficient algorithm, which builds
the sieve not just up to *n*, but up to *p*_{1}×...×*p*_{k-1}×*r*. We will show that even this
less efficient algorithm is still an o(*n*)-time algorithm.

Because we know that each sieve element is generated exactly once and
filtered out at most once, the work done for the *k*'th step in the
algorithm is

Because the work done in all previous steps put together is negligible compared to this, the expression above is a complexity bound for the entire run-time of the algorithm.

This, in turn, is the same as

To prove that this is o(*n*) we merely need to show that

To demonstrate this, consider the logarithm of this value. The logarithm
of 1-1/*p*_{i} is asymptotically
-1/*p*_{i}
for large *i*, so up to a constant multiple, the log of the entire
product behaves as the negative of the sum of the prime harmonic series.

This, in turn, is known to behave, up to an additive constant, as
log(log *k*), which, in turn, diverges, proving our claim.

To calculate the complexity more specifically, we see that the product behaves
as 1/log *k*, where *k* is such that

In complexity terms, this indicates that log *n* is approximately

indicating that *k*≈log *n*.

Hence, the total complexity of the algorithm is on the order of
Θ(*n*/log(log *n*)).

This is, as desired, better than O(*n*), but it is still worse than the
number of primes that are output, which is Θ(*n*/log *n*).

Once again, I thank Jim Boyce for sending in this riddle.

For completion, a Python program implementing the solution can be found
here. (The implementation is not perfect,
in the sense that it uses 'a*b' and 'a+b' without verifying ahead of time that
these values do not exceed *n*, causing a calculation overflow, but this
was done for clarity of presentation only. Readers should find it not
difficult to augment the program so as to avoid these pitfalls.)