HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Project Euler Problem 1

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
problemprojecteuler

Problem

This is my python solution to the first problem on Project Euler:

n = 1
rn = 0
while n < 1000:
    if n%3 == 0 or n%5 == 0:
        rn += n
    n = n + 1
print(rn)


I would like to find a way to keep everything in this python code to as little number of lines as possible (maybe even a one liner??), and possibly improve the speed (it's currently around 12 ms). By the way, this is the problem: 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.Suggestions?
Thanks.

Solution

Python hint number 1:

The pythonic way to do :

n = 1
while n < 1000:
    # something using n
    n = n + 1


is :

for n in range(1,1000):
    # something using n


Python hint number 2:

You could make your code a one-liner by using list comprehension/generators :

print sum(n for n in range(1,1000) if (n%3==0 or n%5==0))


Your code works fine but if instead of 1000, it was a much bigger number, the computation would take much longer. A bit of math would make this more more efficient.

Math hint number 1 :

The sum of all the multiples of 3 or 5 below 1000 is really the sum of (the sum of all the multiples of 3 below 1000) plus (the sum of all the multiples of 5 below 1000) minus the numbers you've counted twice.

Math hint number 2 :

The number you've counted twice are the multiple of 15.

Math hint number 3 :

The sum of the multiple of 3 (or 5 or 15) below 1000 is the sum of an arithmetic progression.

Code Snippets

n = 1
while n < 1000:
    # something using n
    n = n + 1
for n in range(1,1000):
    # something using n
print sum(n for n in range(1,1000) if (n%3==0 or n%5==0))

Context

StackExchange Code Review Q#23379, answer score: 8

Revisions (0)

No revisions yet.