The Sieve of Eratosthenes

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:
And here is a gem from the good old days:
Algorithmically challenged: Sieve of Eratosthenes (the real one) Scala One-Liner

1 Like

@odd Very interesting - Thank you

1 Like

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…

1 Like

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

    m <- 3 to sqrt(n).toInt by 2 if isPrime(m)
    k <- m*3 until n by m*2
  do isPrime -= k


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.

1 Like

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