Project Euler Solutions

ProjectEuler.py

"""These are my solutions to the first 10 problems in Project Euler (https://projecteuler.net/)
I will continue to add more as I solve them
Tobin
02/18/2014
"""


"""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.
"""

def multiples3and5():
	sum = 0
	for x in range(0, 1000):
		if x % 3 == 0 or x % 5 == 0:
			sum += x
	return sum
	
	
"""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.
"""
def sumfibonacci(n):
	one = 0
	two = 1
	temp = 0
	i = 0
	even = 0
	while i < n -1:
		temp = one + two
		one = two
		two = temp
		i += 1
		if temp < 4000000:
			if temp % 2 == 0:
				even += temp
	return even


"""Problem 3: The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
"""
def primefactor(n):
	factors = []
	d = 2
	while n > 1:
		while n % d == 0:
			factors.append(d)
			n /= d
		d += 1
	return max(factors)



"""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.
"""

def product():
	temp = 0
	p = 0
	for x in range(100, 999):
		for y in range(100, 999):
			temp = x * y
			if str(temp) == str(temp)[::-1] and temp > p:
				p = temp
	return p


"""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?
"""

def smallestMultiple(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in range(1, 20)):
            return num
    return "No answer found"


"""Problem 6: 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.
"""

def difSumSquare(num):
	sumSquares = 0
	sums = 0
	for y in range(1, num + 1):
		sums += y
	sums = sums ** 2
	for x in range(1, num + 1):
		sumSquares += x ** 2
	return sums - sumSquares
	
	
"""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 10001st prime number?"""

import time
 
def is_prime(n):
    if n % 2 == 0: return False
    p = 3
    while p < n**0.5+1:
        if n % p == 0: return False
        p += 2
    return True
 
def nth_prime(n):
    prime = 2
    count = 1
    iter = 3
    while count < n:
        if is_prime(iter):
            prime = iter
            count += 1
        iter += 2
    return prime
 
 
"""Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number."""

def findGreatest():
	temp = 0
	number = 7316717653133062491922511967442657474235534919493496983520312774506326239578318
	0169848018694788518438586156078911294949545950173795833195285320880551112540698747158523
	8630507156932909632952274430435576689664895044524452316173185640309871112172238311362229
	8934233803081353362766142828064444866452387493035890729629049156044077239071381051585930
	7960866701724271218839987979087922749219016997208880937766572733300105336788122023542180
	9751254540594752243525849077116705560136048395864467063244157221553975369781797784617406
	4955149290862569321978468622482839722413756570560574902614079729686524145351004748216637
	0484403199890008895243450658541227588666881164271714799244429282308634656748139191231628
	2458617866458359124566529476545682848912883142607690042242190226710556263211111093705442
	1750694165896040807198403850962455444362981230987879927244284909188845801561660979191338
	7549920052406368991256071760605886116467109405077541002256983155200055935729725716362695
	61882670428252483600823257530420752963450
	for x in range(1, 996):
		s = 1
		n = 0
		tempNum = number
		while n < 5:
			s *= tempNum % 10
			tempNum /= 10
			n += 1
		if s > temp:
			temp = s
		number /= 10
	return temp


"""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."""

def pythagoreantriplet(num):
	for x in range(1, 500):
		for y in range(1, 500):
			z = (y**2 + x**2)**0.5
			if x + y + z == 1000:
				return x*y*z


"""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."""

def sumprime(num):
	sumPrime = 0
	for x in range(1, num):
		if isprime(x):
			sumPrime += x
	return sumPrime

def isprime(n):
	n = abs(int(n))
	if n < 2: return False
	if n == 2: return True
	if not n & 1: return False
	for x in range(3, int(n**0.5)+1, 2):
		if n % x == 0:
			return False
	return True