"[the paper] gives a refined version of the sieve that takes less time and less space." It is not about the time-complexity which is "almost" linear in any case (and even slightly worse than the classical version O(nlog(log(n)) vs O(nlog(n)), but about the space complexity, which is "almost" O(n^(1/3)) vs O(n^(1/2) ( or the classical "naive" O(n))