I agree that this is a more efficient way of generating primes in Haskell than the typical Haskell 101 approach. However, I disagree with the idea that the Haskell 101 approach does not deserve to be called an implementation of the "Sieve of Eratosthenes".<p>The distinction is only this: when we have found a prime p and are eliminating numbers accordingly, do we consider ourselves only to spend time directly enumerating the multiples of p and crossing them off? Or do we consider ourselves as running through the entire list and going "Ok, ok, cross, ok, ok, cross, ok, ok, cross" (for, for example, p = 3), thus spending time traversing through multiples and non-multiples alike? So to speak, do we jump from "cross" to "cross", or do we walk along through the "ok"s inbetween?<p>In the former case, each new candidate is worked on only in proportion to its number of prime factors; in the latter case, each new candidate is worked on in proportion to all smaller primes. The former is the more efficient way of generating primes; the latter is (essentially) the ubiquitous, naive approach.<p>But I don't think one can say the traditional understanding of the Sieve of Eratosthenes draws a strong distinction between these two! Traditional accounts would not explicate any difference between "Jump directly from 'cross' to 'cross' " and "Walk from 'cross' to 'cross', saying 'ok' to everything inbetween". It's not a distinction anyone was traditionally worried about. Eratosthenes certainly didn't.<p>So I think both of these are deserving of the name "Sieve of Eratosthenes". They're just different approaches to that sieve.<p>In either case, we say there are primes, to each prime we associate the set of its multiples, we merge these sets into the set of composites, and close the loop of our recursion by noting that the primes are to be the complement of these composites. The difference is, in some sense, arising just from how we represent and manipulate subsets of the naturals (as pertaining to the set of multiples of each prime, as well as their merger into the totality of composites): either as streams of increasing naturals [efficient], or as streams of "In"s and "Out"s [less efficient].