I resumed my code katas – this time, I’m using Erlang to solve the problem:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
It seems to be clever to have a prime number generator for Project Euler anyway. My implementation is based on the Sieve of Erathosthenes and uses the Prime Number Theorem for an estimate on the size of the sieve. The code is pretty easy:
[viewcode]src=pe7.erl [/viewcode]
HTML code generated by vim-color-improved v.0.4.0.Download this code: pe7.erl
In the erathosthenes function, a list comprehension is used to purge all multiplies of the current Index value. My first attempt didn’t include the Index variable – I simply decreased the boundary. The disadvantage of this method is that it keeps the list of primes bigger over the runtime: Instead of removing the multiples of 2 at the very beginning, they get removed as the last multiples. The size of PurgedNumbers stays bigger, which leads to a runtime of 6.7 seconds. When I use the Index variable, the multiples of 2 get removed first which avoids copying them all the way. The runtime decreases to 1.2 seconds (on my Mac Mini).
Since all variables in Erlang are bound only once, I don’t know how to optimize this further. In C, I would use a bit array to further reduce the memory footprint. But: the Erlang code is much easier to read and write. I think Erlang is just not made for low memory bandwidth requirements :-)
The picture above is an representation of the Ulam spiral, CCed on flickr by no_typographic_man.