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:
Post a Comment