Project Euler Problem 351

ATTENTION: Sloppy slow version, takes a while
pfm.totient = Euler's totient function (write that on your own :P )

It states where the product is over the distinct prime numbers dividing n.

import time
import primefacmodule as pfm

start=time.time()

c=[]

def b(n):
 s=0
 for x in xrange(1,n+1):
  t=pfm.totient(x)
  s+=t
 return n*(n-1)/2 + 1 - s
 
def anzahl(n):
 return 6*(n-1)+6*b(n)

print anzahl(100000000)
print time.time()-start

# n*(n-1)/2 + 1 - sum( phi(i), i=1..n)