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

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