Leave the example. But change the blurb to say: This is inspired by the Sieve of Eratosthenes. For a true Sieve of Eratosthenes, see [link to O'Neil].
Unfortunately trial division is in no way inspired by the SoE. It's about the most bruteforcy way to find primes. Basically all it does is to perform a full primality test for every single candidate. The only advantage of the example code is that it uses laziness and sharing to keep a list of the primes found so far to make this trial division slightly less expensive. In fact it can be improved quadratically and still wouldn't be a sieve. On my current machine in 1 second the following code finds the first 60000 primes while the homepage example finds only 3700 primes, both specialised to [Int]: primes = 2 : filter isPrime [3..] where isPrime x = all (\p -> mod x p /= 0) . takeWhile (\p -> p*p <= x) $ primes The SoE on the other hand exploits the global structure of the distribution of a prime's multiples. Without any division at all it simply deduces that after each crossing operation the smallest remaining integer *must* be prime. This is pretty much the same improvement the quadratic sieve makes to Dixon's factoring method and the number field sieve makes to the index calculus method. It gets rid of primality tests and uses the distributions of multiples. Thus it finds lots and lots of relations in one go rather than testing every single relation. It would be equally wrong to call Dixon's method or index calculus sieves. How about simply changing `sieve` to `trialDiv`? It's not that I don't like the given example, because it gives a very small use case for laziness that is difficult enough to reproduce in an eagerly evaluated language. And with the new name for the local function it stops turning the stomach of a number theoretician. Greets, Ertugrul