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)