## 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)
```

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

## 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))```

## 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)```