One of the most frequent recommendations to learn programming is to write code, that is to learn by practice. One way to do that is by solving programming problems. In this post, I will talk about Project Euler, a site full of coding challenges, and my experience with it.
A coding challenge site
Project Euler is a collection of hundreds of mathematical problems intended to be solved using programming. Up to this date, it has more than 700 problems and counting.
“Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics.”
From Project Euler’s site.
While a few of their first problems are relatively easy to solve, they get very challenging quite fast. That’s why I wouldn’t recommend Project Euler for someone who is just starting to learn programming, it can be frustrating. But if you’re already comfortable with the basics of a programming language, then Project Euler is a great way to improve your skills.
Why Project Euler?
What I like about Project Euler is that it pushes you to improve upon your solutions. The problems can be so computationally intensive that, if you don’t use an efficient algorithm, you can run your code for hours before getting a solution or even run out of memory before getting any.
An example: Testing the primality of a number
For example, let’s say we want to determine if a number is prime. We can do that with the following code (using Python):
is_prime = True
for divisor in range(2, number):
if number % divisor == 0:
is_prime = False
break
We are testing all possible divisors between 2 and n. If any of them divides the number we’re testing, then it’s not prime. However, this isn’t efficient because we’re testing more divisors than necessary. Actually, it’s enough to test for divisors up to the square root of the number:
is_prime = True
for divisor in range(2, int(number**.5) + 1):
if number % divisor == 0:
is_prime = False
break
Even then, we’re still testing for redundant divisors. For instance, if we know that the number is not divisible by 2, then it won’t be divisible by any multiple of 2 (4, 6, etc). Same for the rest of the divisors. Actually, to test the primality of a number, the only divisors we need to test are the primes less than the square root of that number. For instance, if we want to test the primality of n², we need to test only the prime numbers up to and including n.
One way to implement this idea is with the Sieve of Eratosthenes. We start with a list of integer numbers starting with 2. We eliminate all multiples of 2. Then we take the next number that hasn’t been eliminated (3 in this case) and delete all of its multiples, and so on. We proceed this way with all of the numbers of the list and the ones that remain at the end are primes.
Let’s see how could we use this idea to get all the primes less than 100:
limit = 100
sieve = [True] * (limit + 1)
primes = []
for n in range(2, limit + 1):
if sieve[n]:
primes.append(n)
multiple = 2*n
while multiple <= limit:
sieve[multiple] = False
multiple += n
sieve is a list of 101 True values. We increase the limit by one because the list starts indexing at n = 0. See that this way sieve[n] will give us the ‘status’ of number n. Then we test all of the numbers starting from n = 2 and proceed by eliminating all of its multiples (sieve[multiple] = False). We do the same with the next value in the sieve that hasn’t been set to False and so on.
We will get:
>>> primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Then we can use this list of primes to test the primality of all numbers up to 10’000 (100²). See how instead of testing hundreds of poossible divisors, we have reduced it to only a few dozen.
These are the kind of improvements that you will be forced to make while solving Project Euler’s problems. Maybe the first approach is good enough to test even large numbers, but you will certainly see the difference as you need to test more and more numbers.
If you would like to see a real Project Euler example, you can see this post.
In conclusion
Project Euler is a great source of challenging mathematics problems that require programming. Either if you just like mathematics and want to learn new subjects or because you want to improve your programming skills, Project Euler is a great option.
nice