If you had asked me what my favorite algorithm was, at any point in the last 6ish years, I would have told you the Sieve of Eratosthenes.
The algorithm’s goal is to find all prime numbers less than some maximum N. Here it is in full:
sieve := an N-length array of booleans, initialized to true
sieve[0] = false
sieve[1] = false
for each p in 2 to N:
if sieve[p]:
for each c in p^2 to N, incrementing by p:
sieve[c] = false
At the end of the algorithm, the primality of every integer from 0 to N is indicated by sieve[n]. You can add a final pass over that array to extract just the primes from it if you need to.
That’s it that’s the whole algorithm, and I love it. It’s very elegant—basically 4 lines plus some simple setup. And it works in a weird way, iterating over and checking the sieve while building it at the same time.
The quick explanation is that we’re counting up and finding prime numbers along the way, starting at the smallest prime we know (2). Every time we find a new prime number p, we just cross off all of its multiples c (seting sieve[c] = false). And we can start that crossing-off at p^2 because any smaller multiple of p would have been caught when we crossed off its smaller prime multiples.
Even cooler is its runtime complexity. You can take a minute to figure it out for yourself but the analysis is weird enough that I wouldn’t expect most people to get an accurate lower bound.
The sieve runs in O(N * log log N). Double log! If you said O(N^2) then you’d be just like me the first time I ran into it. To understand the bound, the first crossing-off (when we find that 2 is prime) does roughly N/2 crosses. The next one does N/3, then N/5, N/7, etc.—in total it’s N times the sum of the reciprocals of primes < N, a series which famously diverges at the very slow rate of log(log(n)).
Nested loop be damned, it’s basically linear. log(log(n)) doesn’t go past 4 until n is roughly one septillion (10^24). If you’re running a sieve that large then I don’t know what to tell you.
Anyway that’s my favorite algorithm. I’ve written it a lot for random Project Euler problems. I do not know how to end this post. I love you, good bye.