Sunday, July 26, 2009

Project Euler and OCaml prime number list generator

Half a year has passed... The main reason why I didn't write anything concerning Ruby golfing is mainly because I stopped practicing quite a while ago, so I do not have any fresh tips to write about now.

Recently, I am mostly spending my time learning the programming languages Clojure and Factor, using them to solve Project Euler problems. Clojure reminds of Scheme, but I am very new to the concatenative paradigm of Factor, as I never learned Forth or any similar language.
Providing a fairly succinct syntax, they perform very well, which is the main reason why I'm now using them over Ruby.

Some weeks ago, this article in which are analyzed the results of the programming language benchmarks game made me want to use again the OCaml language, that I had previously learned and used during my studies at the university. This analysis shows it as an almost ideal programming language in terms of code size vs performance trade-off.

Several problems of the Project Euler deal with prime numbers, so I needed some code to generate them. Unfortunately, I couldn't find any simple prime generating code on the internet: it seems that finding OCaml code snippets is not an easy task...
Here is quite simple implementation of the Sieve of Eratosthenes which is quite fast (even when running only bytecode) and should be enough for most of the problems that require to use prime numbers in the int range:

Which will for example produce the following result:
# let primes = primes_upto 4000000 in
List.nth primes ((List.length primes) - 1);;
- : int = 3999971

For problems requiring bigger primes, but not an exhaustive list of them, using algorithms such as the Miller-Rabin primality test is a better choice.