We solve the very first problem from the Project Euler using C, Python, Erlang and contrast the approaches.
Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.
Many programmers learn C or Java as their first programming language. So, let's try to solve this using C first. We will then program it using Python and Erlang and study the alternate approaches.
int sum = 0;
int i = 0;
while (i < 1000)
if (i%3 == 0 || i%5 == 0)
sum += i;
printf("Sum of all natural numbers below one thousand that are \ multiples of 3 or 5 is: %d\n", sum);
The same program is rewritten in Python as:
total = 0
for i in range(1000):
if i%3 == 0 or i%5 == 0:
total += i
print "Sum of all natural numbers below one thousand that are multiples \
of 3 or 5 is: ", total
Both the above solutions are in the imperative style, wherein we express the solution by telling the language how the final answer has to be computed.
We can restate the problem in a manner fitting to the functional style, where we are concerned about what needs to be done.
"The sum of all the elements of a list which are less than thousand and also, either a multiple of 3 or 5."
Python provides some elements of functional programming via
lambda functions and list comprehensions.
Step 1: Create a list of natural numbers between 1 and 1000.
lst = range(1000)
Step 2: Retain only the multiples of 3 or 5.
Note: Filter function in python takes two parameters, 1. a boolean function, 2. list. In this case, the boolean returns
True if the given number is a multiple of 3 or 5.
return x%3 == 0 or x%5==0
lst2 = filter(ismultiple, lst)
ismultiple can be rewritten as an anonymous function using
lst2 = filter(lambda x: x%3==0 or x%5==0, lst)
Step 3: Add up the multiples of 3 and 5 less than 1000
reduce(function, sequence[, initial]) -> value
Apply a function of two arguments cumulatively to the items of a sequence, from left to right, so as to reduce the sequence to a single value.
from operator import add
lst3 = reduce(add, lst2)
Putting this all together,
from operator import add
total = reduce(add, filter(lambda x: x%3==0 or x%5==0, range(1000)))
While the above solution illustrates the use of functional style, it does not feel pythonic enough. We rewrite the above program using list comprehensions, which is arguably more readable.
total = sum([x for x in range(1000) if x%3==0 or x%5==0])
Now that we are familiar with functional approach to solving this problem, let's try to write an Erlang program to do the same.
Step 1: Generate the list of natural numbers less than 1000.
Lst = lists:seq(1,1000).
Step 2: Retain only the multiples of 3 and 5.
Lst2 = [A|| A <- lists:seq(1,999), (A rem 3 =:= 0) or (A rem 5 =:= 0)].
Step 3: Add up
Lst3 = lists:sum( [A|| A <- lists:seq(1,999), (A rem 3 =:= 0) or (A rem 5 =:= 0)]).
Note: The programming exercise itself is trivial, but I hope comparing three languages and two methods will make this slightly more interesting, at least to the novice programmer. I wrote up this as an exercise in writing and editing for clarity.
© 2003-2011 Pradeep Gowda