Euler 72

gistfile1.txt

# http://projecteuler.net/problem=72
# i got to thinking that this is really just asking to take a sum of euleur's totient from 2 to 1MM
# and that turns out to be true.

factors = [1]*1000001
for i in range (0,len(factors)):
	factors[i]=i


# set up prime sieve to n
n=1000000
myPrimes = [True]*(n+1)
last = 0
for i in range (2,n):
	if myPrimes[i] == True:
		factors[i] = i-1
		j = 2*i
		while j<=n:
			myPrimes[j]=False
			factors[j]=factors[j]*(1.0-(1.0/i))
			j=j+i	

print sum(factors[2:n+1])