Menu

Subscribe

Project Euler Problem 5

on project euler, erlang, perl, python

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Link to original description
Source code examples on Github

Erlang version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p4
% vim:syn=erlang

-mode(compile).

main(_) ->
    Answer = lists:foldl(fun(A,B)-> A*B end, 1, filter(lists:seq(2,20))),
    io:format("Answer ~p ~n",[ Answer ]).

filter([])    -> [];
filter([H|T]) -> [H | filter([ divide(X,H) || X <- T])].

divide(A, B) when A rem B =:= 0 -> A div B;
divide(A, _) -> A.

Erlang version 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p5_1
% vim:syn=erlang

-mode(compile).

main(_) ->
    Answer = lists:foldl(fun(A, B) -> A * B div gcd(A, B) end,1,lists:seq(2,20)),
    io:format("Answer ~p ~n",[ Answer ]).

gcd(A, B) when B > 0 -> gcd(B, A rem B);
gcd(A, _) -> A.

Perl version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/perl
use strict;

sub gcd{
    my ($a, $b, @r) = @_;
    @r ? gcd($a, gcd($b,@r)) : $b == 0 ? $a : gcd($b, $a % $b)
}

sub lcm{
    my ($a, $b, @r) = @_;    
    @r ? lcm($a, lcm($b, @r)): $a * $b / gcd($a, $b)
}

print "Answer".lcm(1 .. 20)."\n";

Python version

1
2
3
4
5
6
7
8
9
10
11
#!/usr/bin/python

# Euclid's algorithm
def gcd(a, b): return b and gcd(b, a % b) or a 
def lcm(a, b): return a * b / gcd(a, b)

answer = 1
for i in xrange(1,21): answer = lcm(answer,i)

print "Answer %d " % answer