Solution to Euler project in Python
Problem 1-10
[sourcecode language=”python”]
## For class Helper see below
helperObj = Helper()
def problem1(self):
”’
Add all the natural numbers below one thousand
that are multiples of 3 or 5.
”’
numbers = range(0,1000)
return reduce(lambda x,y: x+y, filter(lambda(x):x%3==0 or x%5==0, numbers))
def problem2(self):
”’
By considering the terms in the Fibonacci sequence whose values do
not exceed four million, find the sum of the even-valued terms.
”’
index = 1
fibNumbers = []
while(True):
value = helperObj.fib(index)
if value < 4000000:
fibNumbers.append(helperObj.fib(index))
index+=1
else:
break
return reduce(lambda x,y: x+y, filter(lambda(x):x%2==0, fibNumbers))
def problem3(self):
”’
What is the largest prime factor of the number 600851475143 ?
”’
factors = helperObj.factors(600851475143)
index = -1
while(True):
if helperObj.isPrime(factors[index]) == 0:
return factors[index]
else:
index -= 1
continue
def problem4(self):
”’
Find the largest palindrome made from the product
of two 3-digit numbers.
”’
largestNumber = 999
max = 0
while(largestNumber > 300):
counter = 999
while(counter > 300):
if helperObj.isPalindrome(largestNumber * counter):
p = largestNumber*counter
if p > max:
max = p
counter = counter – 1
largestNumber -= 1
return max
def problem5(self):
”’
What is the smallest positive number that is evenly divisible
by all of the numbers from 1 to 20?
”’
return reduce(helperObj.lcm, range(1, 20+1))
def problem6(self):
”’
Find the difference between the sum of the squares of the first
one hundred natural numbers and the square of the sum.
”’
return helperObj.sumOfSquares(100) – helperObj.sumOfNumbers(100) ** 2
def problem7(self):
”’
What is the 10001st prime number?
”’
index = 0
num = 2
while(index < 10001):
if helperObj.isPrime(num) == 0:
index += 1
num += 1
return num-1
def problem8(self):
”’
Find the greatest product of five consecutive digits
in the 1000-digit number.
”’
num = "73167176531330624919225119674426574742355349194934" + \
"96983520312774506326239578318016984801869478851843" + \
"85861560789112949495459501737958331952853208805511" + \
"12540698747158523863050715693290963295227443043557" + \
"66896648950445244523161731856403098711121722383113" + \
"62229893423380308135336276614282806444486645238749" + \
"30358907296290491560440772390713810515859307960866" + \
"70172427121883998797908792274921901699720888093776" + \
"65727333001053367881220235421809751254540594752243" + \
"52584907711670556013604839586446706324415722155397" + \
"53697817977846174064955149290862569321978468622482" + \
"83972241375657056057490261407972968652414535100474" + \
"82166370484403199890008895243450658541227588666881" + \
"16427171479924442928230863465674813919123162824586" + \
"17866458359124566529476545682848912883142607690042" + \
"24219022671055626321111109370544217506941658960408" + \
"07198403850962455444362981230987879927244284909188" + \
"84580156166097919133875499200524063689912560717606" + \
"05886116467109405077541002256983155200055935729725" + \
"71636269561882670428252483600823257530420752963450"
max = 0
for index in range(0,995):
product = reduce(lambda x,y: int(x)*int(y), list(num[index:index+5]))
if product > max:
max = product
return max
def problem9(self):
”’
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
”’
for a in range(1,1001):
for b in range(1,1001):
c = 1000 – (a+b)
if helperObj.isPythagorean(a,b,c) == 0:
return a*b*c
def problem10(self):
”’
Find the sum of all the primes below two million
”’
sum = 0
for x in xrange(3,2000000+1, +2):
if helperObj.isPrime(x) == 0:
sum += x
return sum + 2
listOfProblems = [1,3,5]
for i in listOfProblems:
print eval("problem" + str(i) + "()")
class Helper:
”’
Helper class used in solutions
”’
def fib(self, number):
if number==1:
return 1
if number==2:
return 2
return self.fib(number-2) + self.fib(number-1)
def factors(self, number):
list = []
for num in range(2,int(number**0.5)):
if number%num == 0:
list.append(num)
return list
def isPrime(self, number):
for num in range(2,number-1):
if number%num == 0:
return -1
else:
continue
return 0
def isPalindrome(self,number):
number = str(number)
return number == number[::-1]
def sumOfNumbers(self, number):
return (number * (number+1))/2
def sumOfSquares(self,number):
return (number * (number+1) * (2*number+1))/6
def isPythagorean(self, num1, num2, num3):
if num3**2 == num2**2 + num1**2:
return 0
else:
return -1
def gcd(self, a, b):
return (self.gcd(b,a%b) if b else a)
def lcm(self, a, b):
return (a*b) / self.gcd(a,b)
[/sourcecode]
