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

multiples = []

for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        multiples.append(i)

# print(sum(multiples))


# Problem 2: Even Fibonacci numbers
# Each new term in the Fibonacci sequence is generated by adding the previous two terms.
#
# By considering the terms in the Fibonacci sequence whose values do not exceed four million,
# find the sum of the even-valued terms.

fib = [0, 1]
n = 2
while True:
    newfib = fib[n-1] + fib[n-2]
    if newfib < 4000000:
        fib.append(newfib)
        n += 1
    else:
        break
# print(sum([num for num in fib if num % 2 == 0]))


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

huge = 600851475143

# Borrowed prime-finding code :(
primes = []
for possiblePrime in range(2, 10000 + 1):
    # Assume number is prime until shown it is not.
    isPrime = True
    for num in range(2, int(possiblePrime ** 0.5) + 1):
        if possiblePrime % num == 0:
            isPrime = False
            break
    if isPrime:
        primes.append(possiblePrime)


def reduce(number):
    factor_list = [number]
    while max(factor_list) not in primes:
        largest = max(factor_list)
        factor_list.remove(largest)

        factors = []
        for prime in primes:
            if largest % prime == 0:
                factors.append(prime)
        for factor in factors:
            largest = largest / factor
        if largest != 1:
            factors.append(int(largest))
        factor_list += factors
    return factor_list


print(reduce(huge))

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

palindromes = []
rows = cols = [i for i in range(100, 1000)]

for col in cols:
    for row in rows:
        value = str(row * col)
        if value[0] == value[-1] and value[1] == value[-2] and value[2] == value[-3]:
            palindromes.append(int(value))

# print(max(palindromes))


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

def lcm(x, y):
    if x > y:
        greater = x
    elif y > x:
        greater = y
    while greater % x != 0 or greater % y != 0:
        greater += 1
    return greater

numbers = [i for i in range(1, 21)]
numbers.reverse()

solution = 1
for number in numbers:
    solution = lcm(solution, number)

print(solution)
