Euler Problem 69

gistfile1.txt

# http://projecteuler.net/problem=69

# first set up a special sieve- factors[j] is the totient for each number
factors = [1]*1000001
n=1000000
myPrimes = [True]*(n+1)
last = 0
for i in range (2,n):
	if myPrimes[i] == True:
		j = 2*i
		while j<=n:
			myPrimes[j]=False
			factors[j]=factors[j]/(1.0-(1.0/i))
			j=j+i	

# find the largest number in the list, and it's index # 
max=0
max_a=0
for a in range (0,len(factors)):
	if factors[a]>max:
		max = factors[a]
		max_a=a

print max,max_a