Monday, January 12, 2009

Erlang solution for Euler problem 7

Euler problem 7 asks us to find the 10001st prime number.

Once again, my Erlang solution uses the brute force approach with a few optimizations.

I check all odd numbers for being a prime number until I find the 10001st prime.

To check whether number n is prime, I try to divide it by all numbers from 2 thru sqrt(n).

Here is the brute force Erlang program:

%% Project Euler, problem 7
%%
%% 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?

-module(euler7).
-author('Cayle Spandon').

-export([solve/0, findNthPrime/1]).

isPrime(N) ->
MaxTry = trunc(math:sqrt(N)),
isPrime(N, 2, MaxTry).

isPrime(N, Try, MaxTry) ->
if
Try > MaxTry ->
true;
true ->
if
N rem Try == 0 ->
false;
true ->
isPrime(N, Try+1, MaxTry)
end
end.

findNthPrime(PrimesNeeded) ->
findNthPrime(PrimesNeeded, 3, 1, 2). %% Treat 2 as a special case: it is the only even prime.

findNthPrime(PrimesNeeded, Try, PrimesFound, LastPrimeFound) ->
if
PrimesFound == PrimesNeeded ->
LastPrimeFound;
true ->
case isPrime(Try) of
true -> findNthPrime(PrimesNeeded, Try+2, PrimesFound+1, Try);
false -> findNthPrime(PrimesNeeded, Try+2, PrimesFound, LastPrimeFound)
end
end.

solve() ->
findNthPrime(10001).


I was aware of the sieve of Eratosthenes as a method to find all prime numbers up to some number n (which is not exactly the same question as Euler problem 7) but I did not know how to implement it in Erlang. It turns out that there there is a stack overflow question which discusses this and contains several example implementations. There is also this excellent article on implementing the sieve in functional languages.

No comments: