I’m working to bone up on my python skills so I decided to spend my Sunday doing problems 1-10 from Project Euler. I’ve done them before with C or Java but this was my first time with Python. Here are the problems and my commented code for each one in case it interests anybody.
Problem 1 – Multiples of 3 and 5
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. ANSWER = 233168.
# Project Euler - Question 1 - Multiples of 3 & 5
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=1
# 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. ANSWER = 2318.
sum = 0 #variable to hold sum
# Iterate i from 0 to 99
# If i is divisible by 3 or 5, add to sum
for i in range(100):
if (i%3 == 0 or i%5==0):
sum += i
# Print answer
print('The sum is: ' + str(sum))
Problem 2 – Even Fibonacci Numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. ANSWER = 4613732
# Project Euler - Question 2 - Even Fibonacci Numbers
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=2
# Each new term in the Fibonacci sequence is generated by
# adding the previous two terms. By starting with 1 and 2,
# the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
# By considering the terms in the Fibonacci sequence whose values do
# not exceed four million, find the sum of the even-valued terms.
# Answer = 4613732
sum = 0 # Variable to hold sum
num1 = 0; # First number
num2 = 1; # Second number
# While the second number is less than 4000000
# This ensures the first number is less after moving
while num2 < 4e6:
# Method 1 of incrementing numbers
temp = num1
num1 = num2
num2 = num1 + temp
# Method 2:
# num1, num2 = num2, num1+num2
# If the number is eve, add to sum
if(num1%2 == 0):
sum += num1
# Print results
print('The sum is: ' + str(sum))
Problem 3 – Largest Prime Factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143? ANSWER = 6857
# Project Euler - Question 3 - Largest Prime Factor # Written by Matthew Walker, 20 August 2017 # https://projecteuler.net/problem=3 # The prime factors of 13195 are 5, 7, 13 and 29. # What is the largest prime factor of the number 600851475143? # Answer = 6857 # Import math library to get sqrt import math # isPrime function - returns True or False def isPrime(num): # Iterates from 2 to sqrt(num)+1 as discussed in #7 # Make sure to convert sqrt to int for range # Using xrange will save considerable time for large numbers for i in xrange(2,int(math.sqrt(num))+1): if (num % i == 0): return False return True # List with factors, starts with only one factors = [600851475143] # Infinite loop, will break out when necessary while True: # If the largest factor (0 spot) is prime, break if(isPrime(factors[0])): break # Try to divide the largest factor by numbers starting with 2 # If a number evenly divide, reduct the largest factor and # append the divisor to the end of the list, break out of for # loop and start again at 2 with the new largest factor for i in xrange(2,factors[0]): if (factors[0] % i == 0): factors[0] = factors[0] / i factors.append(i) break # Sort factors and print them factors.sort() print(factors)
Problem 4 – Largest Palindrome Product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers. ANSWER = 906609
# Project Euler - Question 4 - Largest Palindromic Product
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=4
# A palindromic number reads the same both ways.
# The largest palindrome made from the product
# of two 2-digit numbers is 9009 = 91 x 99.
# Find the largest palindrome made from the product of two 3-digit numbers.
# ANSWER: 913 * 993 = 906609. Took 1.0s
# isPal function returns True or False
# Converts number to string and iterates through half of it
# If characters don't match return false
def isPal(num):
numString = str(num)
for i in range(0,len(numString)/2+1):
if (numString[i] != numString[-i-1]):
return False
return True
# Keep track of max product
maxProduct = 0
# Keep track of values used for max prodcut
max1, max2 = 0,0
# Iterate from 999 to 99 going down for both values
# Generate a product and determine if it's a palindrome
# If it is a palindrom, determine if it is max
for i in range(999, 99, -1):
for j in range(999, 99, -1):
product = i * j
if isPal(product):
if(product > maxProduct):
maxProduct = product
max1, max2 = i, j
# Print snswers
print('The largest palindromic product is: ' + str(maxProduct))
print(str(maxProduct) + ' = ' + str(max1) + ' * ' + str(max2))
Problem 5 – 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? ANSWER = 232,792,560
# Project Euler - Question 5 - Smallest Multiple
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=5
# 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?
# Answer = 232,792,560
# First time I wrote this I started from 1 going up and
# divided by all the numbers from 1 up to 20 and counted
# number of multiples. If it got to 20 it stopped and printed
# Took about (290) to run.
# Second time I wrote it, I started from 1 going up and
# divided by all the numbers from 20 down to 1 and counted
# number of multiples and if I got to 20 it stopped and printed
# Took about 224 seconds to run. This speeds it up because a number
# is less likely to be divisible by 20 or 19 than by 1 or 2 so by starting
# at the top you rule out that number quicker and move on.
# Third time I wrote it, I started from 1 going up and
# divided by all the numbers from 20 down to 11 and counted
# number of multiples and if I got to 10 it stopped and printed
# Took about 210 seconds to run. This speeds it up because if a number
# is divisible by 20, it's also divisible by 10, by 18 it's also by 9,
# by 16, it's also by 8, etc. So we don't need to test for 1-10
# Forth time I wrote it, I started from 20 going up by 20 and
# divided by all the numbers from 20 down to 11 and counted
# number of multiples and if I got to 10 it stopped and printed
# Took about 14 seconds to run. We can do this because all of these
# numbers must be divisible by 20 so checking anything between the multiples
# of twenty is a waste of time.
# Fifth time I wrote it, I started from 2520 going up by 2520 and
# divided by all the numbers from 20 down to 11 and counted
# number of multiples and if I got to 10 it stopped and printed
# Took about 0.2 seconds to run. We can start at 2520 since the
# problem tells us that is the lowest number for 1-10 multiples
# and since 1-20 includes 1-10, it can't be less. We can increase
# by 2520 for the same reason.
# The code below is from the forth time I wrote it with two
# solutions using different techniques
# ------------------------------------------------------
# First solution --------------------------------------
# ------------------------------------------------------
num = 0
# Infinite Loop because we don't know the max
# We will use a break when we find the first number
# Could also do a for loop up to 20! but this is easier
while True:
#increment num by 20 each time
num += 20
# NumMultiples keeps track of the number of multiples for num
numMultiples = 0
# Iterate from 20 to 11 going down by 1
for i in range(20,10, -1):
# If the number is divisible by i then increase
# the number of multiples num has.
if (num % i == 0):
numMultiples+=1
else:
# If not evenly divisible, break to save time
break;
# If there were 10 multiples that means it's evenly
# divisibly by all the numbers so we break out of while
if (numMultiples == 10):
break;
# Print out current num to keep track (in millions)
if num % 1000000 == 0:
print(num/1000000)
print('The lowest common multiple is: ' + str(num))
# ------------------------------------------------------
# Second solution --------------------------------------
# ------------------------------------------------------
num = 0
keepGoing = True
# In this version, we go until the boolean keepGoing is changed to False
while keepGoing:
#increment num by 20 each time
num += 20
# NumMultiples keeps track of the number of multiples for num
numMultiples = 0
# Iterate from 20 to 11 going down by 1
for i in range(20,10, -1):
if (num % i != 0):
# If not evenly divisible, break out of for loop
# because we know it isn't the LCM
break
if (i == 11):
# If we reached here without breaking, then we've
# found the number we're looking for.
# Change keepGoing to False to break out of while loop
keepGoing = False
break
# Print out current num to keep track (in millions)
if num % 1000000 == 0:
print(num/1000000)
print('The lowest common multiple is: ' + str(num))
Problem 6 – Sum Square Difference
The sum of the squares of the first ten natural numbers is, 12 + 22 + … + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + … + 10)2 = 552 = 3025 Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum. ANSWER = 25164150
# Project Euler - Question 6 - Sum Square Difference
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=6
# The sum of the squares of the first ten natural numbers is,
# 1^2 + 2^2 + ... + 10^2 = 385
# The square of the sum of the first ten natural numbers is,
# (1 + 2 + ... + 10)^2 = 55^2 = 3025
# Hence the difference between the sum of the squares of the first
# ten natural numbers and the square of the sum is 3025 - 385 = 2640.
# Find the difference between the sum of the squares of the
# first one hundred natural numbers and the square of the sum.
# ANSWER = 25,164,150
# Keep track of the sum of the squares
sumSquare = 0
# Keep track of the the sums
sums = 0
# Iterate through numbers [1:100] 1-100 inclusevely
for i in range(1,101):
sumSquare += i*i
sums += i
# Square the individuals sums to find square of sums
squareSum = sums * sums
# Print answers
print('The sum of the squares is: ' + str(sumSquare))
print('The square of the sums is: ' + str(sums))
print('The difference is: ' + str(squareSum - sumSquare))
Problem 7 – 10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10,001st prime number? ANSWER = 104,743
# Project Euler - Question 7 - 10,001st prime
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=7
# By listing the first six prime numbers:
# 2, 3, 5, 7, 11, and 13,
# we can see that the 6th prime is 13.
# What is the 10,001st prime number?
# ANSWER = 104,743
# Took 102s in first version.
# In the first version, I checked for primes from
# two to num.
# In the second version, I checked for primes from
# two to num/2+1.
# In the third version, I checked for primes from
# two to sqrt(num)+1.
# Version 1: 102s
# Version 2: 44s
# Version 3: 0.5s
# Import math library to get sqrt
import math
# isPrime function - returns True or False
def isPrime(num):
# Iterates from 2 to sqrt(num)+1 as discussed above
# Make sure to convert sqrt to int for range
for i in range(2,int(math.sqrt(num))+1):
if (num % i == 0):
return False
return True
count = 1 # Number of primes
num = 2 # Prime number (count)
# While loop to continue until we reach 100001th prime
while (count<10001):
num+=1
if isPrime(num):
#print('Found a prime: ' + str(num) + ', prime number: ' + str(count))
# If a prime is found, increase count and continue
count+=1
# Print answer
print('The 10001th prime is: ' + str(num))
Problem 8 – Largest Product in a Series
The four adjacent digits in the 1000-digit number (below) that have the greatest product are 9 × 9 × 8 × 9 = 5832. Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product? ANSWER = 23,514,624,000
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
# Project Euler - Question 8 - Largest Product in a Series
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=8
# The four adjacent digits in the 1000-digit number that
# have the greatest product are 9 x 9 x 8 x 9 = 5832.
# 73167176531330624919225119674426574742355349194934
# 96983520312774506326239578318016984801869478851843
# 85861560789112949495459501737958331952853208805511
# 12540698747158523863050715693290963295227443043557
# 66896648950445244523161731856403098711121722383113
# 62229893423380308135336276614282806444486645238749
# 30358907296290491560440772390713810515859307960866
# 70172427121883998797908792274921901699720888093776
# 65727333001053367881220235421809751254540594752243
# 52584907711670556013604839586446706324415722155397
# 53697817977846174064955149290862569321978468622482
# 83972241375657056057490261407972968652414535100474
# 82166370484403199890008895243450658541227588666881
# 16427171479924442928230863465674813919123162824586
# 17866458359124566529476545682848912883142607690042
# 24219022671055626321111109370544217506941658960408
# 07198403850962455444362981230987879927244284909188
# 84580156166097919133875499200524063689912560717606
# 05886116467109405077541002256983155200055935729725
# 71636269561882670428252483600823257530420752963450
# Find the thirteen adjacent digits in the 1000-digit
# number that have the greatest product.
# What is the value of this product?
# ANSWER = 23,514,624,000. Took 0.1s
# findProduct function takes a string and returns
# the product of every digit
def findProduct(numString):
product = 1
for i in range(len(numString)):
product = product * int(numString[i])
return product
# The number we need in int and string form
bigNum = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
bigString = str(bigNum)
# Variables to track things
maxProduct = 0
product = 0
numChars = 13
# Iterate over the 1000 digits except for the end digits
# For each iteration find the string of numChar length and
# pass it to the function to find product
for i in range(len(bigString)-numChars):
product = findProduct(bigString[i:i+numChars])
# If a product is larger than max, store it
if (product > maxProduct):
maxProduct = product
# Print answers
print('Max Product of ' + str(numChars) + ' digits is: ' + str(maxProduct))
Problem 9 – Special Pythagorean Triplet
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc. ANSWER = 31,875,000
# Project Euler - Question 9 - Special Pythagorean Triplet
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=9
# A Pythagorean triplet is a set of three natural numbers,
# a < b < c, for which, a2 + b2 = c2
# For example, 32 + 42 = 9 + 16 = 25 = 52.
# There exists exactly one Pythagorean triplet for which
# a + b + c = 1000. Find the product abc.
# Answer = 31,875,000 Took 21 seconds. (10s with exit())
# Iterate a from 1 to 1000
# Then iterate b from a to 1000
# Then iterate c from b to 1000
# This is because a < b < c. Otherwise it would take
# much much longer and return two answers
for a in range(1,1000):
for b in range(a,1000):
for c in range (b, 1000):
# Once we have an iteration of a, b, and c
# Determine if it fits the criteria of a+b+c==1000 and
# a^2 + b^2 == c^2
# Test a+b+c first because it is a faster test. Takes ~half the time
if (a+b+c == 1000):
if (a*a + b*b == c*c):
# Print answers
print('A: ' + str(a) + ' B: ' + str(b) + ' C: ' + str(c))
print('Product is: ' + str(a*b*c))
# If we found it, exit to save time
exit()
Problem 10 – Summation of Primes
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. ANSWER = 142,913,828,922
# Project Euler - Question 10 - Summation of Primes
# Written by Matthew Walker, 20 August 2017
# https://projecteuler.net/problem=10
# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
# Find the sum of all the primes below two million.
# ANSWER = 142,913,828,922 Took 14 seconds.
# Using xrange in isPrime function saves considerable time.
# 29s using just range, 20s using range but omitting odds
# 14s using xrange, 13.5s using xrange and omitting odds
# Import math library to get sqrt
import math
# isPrime function - returns True or False
def isPrime(num):
# Iterates from 2 to sqrt(num)+1 as discussed in #7
# Make sure to convert sqrt to int for range
# Using xrange will save considerable time for large numbers
for i in xrange(2,int(math.sqrt(num))+1):
if (num % i == 0):
return False
return True
sum = 0
# Iterate from 2 to two million
# You can increase speed slightly by starting at 3 and
# iterating by 2 to skip evens but only saves 0.5s
for i in range(2,2000000):
# If number is prime, add to sum
if isPrime(i):
sum += i
# Print out results
print('The sum of all primes below 2 million is: ' + str(sum))
The Wandering Engineer 
Hi! I am a student and I am having trouble understanding what happens in your solution for problem 5. And when I plugged in that same code, it printed all whole numbers from 1.0 to 230.0, and than printed the number. Can you explain why that happens?
Sure. If you look at line 79 you’ll see that it’s printing out what number it is on so that I can track how it’s progressing and I know it wasn’t hung up on something. It’s only printing every million numbers to save time and I just left off the million part for some reason. Hope that helps.