Python solution to Project Euler problem number 5

Solution

def is_prime(x, primes):
    for p in primes:
        if x % p == 0:
            return False
    return True

assert is_prime(3, [2])
assert not is_prime(4, [2, 3])

def smallest_common_multiple_of_all_numbers_up_to(x):
    if x == 1:
        return 1
    y = 1
    primes = []
    for i in range(2, x + 1):
        if is_prime(i, primes):
            primes.append(i)
            y *= i
            continue
        if y % i == 0:
            continue
        for p in primes:
            if (y * p) % i == 0:
                y *= p
                break
    return y

assert smallest_common_multiple_of_all_numbers_up_to(3) == 6
assert smallest_common_multiple_of_all_numbers_up_to(10) == 2520

print smallest_common_multiple_of_all_numbers_up_to(20)

Solution to Project Euler problem number 4 in Python

Solution

def reverse(number):
    result = 0
    while number > 0:
        result = result * 10 + (number % 10)
        number = int(number / 10)
    return result

def is_palindrome(number):
    return number == reverse(number)

largestPalindrome = 0
a = 999
while a >= 100:
    if a % 11 == 0:
        b = 999
        db = 1
    else:
        b = 990
        db = 11 
    while b >= a:
        if a*b <= largestPalindrome:
            break
        if is_palindrome(a*b):
            largestPalindrome = a*b
            b = b-db
        a = a-1
print largestPalindrome

Solution for Project Euler's problem number 6 in Python

Problem 6 - Sum square difference

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

Solution

its time complexity is O(n) (linear)

it's under a second for 10,000 but it takes a while for 100,000

def sum(an):
    n = int(an / 2)
    return n * (1 + an)

def sum_square(an):
    sum = 0
    for i in range(1, an + 1):
        sum += i ** 2
    return sum

def problem6(an):
    return sum(an) ** 2 - sum_square(an) 
    
print problem6(100)

Solution for Project Euler's problem number 3 in Python

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 ?

Simplest solution

its time complexity is O(n) (linear) with the largest factor

It means it's fast for 600851475143 but not for 600851475145

def get_prime_factors(number):
    factor=2
    while number <> 1 & factor <= number:
        factor += 1
        while number % factor == 0:
            yield factor
            number /= factor

for x in get_prime_factors(600851475143):
    print x

Fastest solution

its time complexity is O(sqrt(n)) (fractional power) with the largest factor.

def get_prime_factors(number):
    while number % 2 == 0:
        yield 2
        number /= 2
    factor=1
    maxFactor = int(number ** .5)
    while number <> 1 & factor <= maxFactor:
        factor += 2
        while number % factor == 0:
            yield factor
            number /= factor
    if number > 1:
        yield number    

for x in get_prime_factors(600851475145):
    print x

Solution in Python for Project Euler's problem #2

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.

Python solution

it is very fast even for numbers up to 1e200

def fibsum(maximum):
    fib1 = 0
    fib2 = 1
    sum = 0
    while fib2 < maximum:
        aux = fib2
        fib2 += fib1
        fib1 = aux
        if fib2 & 1 == 0:
            sum += fib2
    return sum
        
print fibsum(int(4e6))

Python solution for Project Euler's problem #1

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.

Iterative solution

it gets very slow for 1,000,000 because its time complexity is O(n) (linear)

def sum(maximum, multiplier):
    sum = 0
    for x in range(multiplier, maximum, multiplier):
        sum += x
    return sum
    
target = 1000
print sum(target, 3) + sum(target, 5) - sum(target, 3 * 5)

Fastest solution

it never gets slow because its time complexity is O(1) (constant)

def sum(maximum, interval):
    maximum -= 1
    an = maximum - (maximum % interval)
    n = int(maximum / interval)
    return n * (interval + an) / 2
        
target = 1000
print sum(target, 3) + sum(target, 5) - sum(target, 3 * 5)