Euler #72

def factorize(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = int(n / 2)
    for x in range(3, int(n ** 0.5) + 1, 2):
        while n % x == 0:
            n = int(n / x)
            factors.append(x)
    if n > 2:
        factors.append(int(n))
    return set(factors)


def totient(n):
    coprimes = n
    for x in factorize(n):
        coprimes *= (1 - (1 / x))
    return round(coprimes)

answer = -1
for a in range(1, 10**6+1):
    print(a)
    answer += a
    answer -= (a - totient(a))
print(answer)