How the effort required to read an understand the Sieve of Eratosthenes varies greatly depending on the programming paradigm used to implement the algorithm.

Related reading: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

And here is a gem from the good old days:

Algorithmically challenged: Sieve of Eratosthenes (the real one) Scala One-Liner

new slide deck: The Sieve of Eratosthenes - Part II - Genuine versus Unfaithful Sieve - thank you @odd for pointing me to the paper “The Genuine Sieve of Eratosthenes” - download for best viewing The Sieve of Eratosthenes - Part II - Genuine versus Unfaithful Sieve…

I agree with the general sentiment, but for what it’s worth, the imperative example seems like a cherry-picked strawman. Here is a *mutable* scala implementation that is significantly more efficient, but still concise and a lot more understandable than the java sample:

```
def primesUntil(n: Int): collection.BitSet = {
val isPrime = collection.mutable.BitSet(n)
// optimize sieve by considering only odd numbers
(3 until n by 2).foreach(isPrime += _)
isPrime += 2
for
m <- 3 to sqrt(n).toInt by 2 if isPrime(m)
k <- m*3 until n by m*2
do isPrime -= k
isPrime
}
```

Modern java can look look a lot more like what I’ve written. How much less maintainable is this than the functional version? (could rename `m`

to `nextPrime`

and k to `multiple`

for clarity)

Related post - Sieve of Eratosthenes: Finding All Prime Numbers - InterviewBit for finding all prime numbers with different approaches.

Thank you @stewSquared.

One thing that fascinates me is the possibility that in the past (some) people might have spent decades in a one-paradigm bubble, in which they were only exposed to particular approaches