Goal

This blog helps people understand how projecteuler.net works, and provides a basic solution of problem 1 in Python with explanations.

About Project Euler

projecteuler.net is a website that offers series of challenging mathematical/computer programming problems. It aims to help the audiences arrive at elegant and efficient methods, understand the use of a computer, and approach programming skills, in order to solve most problems.

Get Stated

An account could be simply registered if you do not have one. If you already have an account, please sign in directly. Under the section of Archives, the questions are sorted based on their ID number.

Problem 1 - Multiples of 3 and 5

Problem Description If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Mathematical Solution

The statement of the problem is to sum the multiples of 3 and 5 below 1000, not up to and equal 1000. The problem could be solved in 4 steps.

Step 1:

Stop thinking on the number 1000 and turn your attention to the number 990 instead. If you solve the problem for 990 you just have to add 993,995,996 & 999 to it for the final answer. This sum is (a) = 3983

Step 2:

Count all the numbers divisible by 3: From 3… to 990 there are 330 terms. The sum is 330 * (990 + 3) / 2, so (b) = 163845

Step 3:

Count all the numbers divisible by 5: From 5… to 990 there are 198 terms. The sum is 198 * (990 + 5) / 2, so © = 98505

Step 4:

However, the GCD (greatest common divisor) of 3 and 5 is 1, and the LCM (least common multiple) is 3 × 5 = 15. This means every number that divides by 15 was counted twice, and it should be done only once. Because of this, you have an extra set of numbers started with 15 all the way to 990 that has to be removed from both (b) and ©.

Then, from 15… to 990 there are 66 terms and their sum is 66 * (990+15) / 2, so (d) = 33165 The answer for the problem is: (a) + (b) + © − (d) = 233168

Programming Solution

It seems that the mathematical solution is a bit slow with many calculation involved and time consuming. Now let consider about programming aspect, so that we have a change to escape from heavy math:)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# Declare a variable named sum, and initial it to zero (0)
sum = 0

# A for-loop to search numbers from 1 to 999
for i in range(1, 1000):

# Check whether the selected number is divisible by 3 or 5
    if (i % 3 == 0 or i % 5 == 0):
    
# If the number is divisible by 3 or 5, add the number up to sum
        sum += i

# Return the final result
return sum