The Sieve of Eratosthenes is a neat way to find all of the prime numbers below some number. If you do it on paper (and I suggest you do), you can easily find all primes below 100 within a few minutes. The challenge this week is to write a version in Clojure that lets you calculate all the primes below a given number n
.
The biggest challenge with this is that you might run into problems with stack overflows or speed. Make sure the algorithm can still run with n=100,000
.
I'd love to see your answers. Bonus points for creative and innovative solutions. I'll share the best next week. Fire up a REPL, try it out, and send me your answers. (Please note that, unless you tell me otherwise, I will share your name in the newsletter if you send me an answer.)
Here's a parallellized (when it comes to sieving the sieve) solution.
Here are quick-bench runs for sieving 100K numbers, 1 million, and 10 million on my machine:
The last one was to check what the overhead is for collecting a thread. Doesn't seem to matter much for this case.