It took me several tries to come up with the most efficient way to get Euler’s totient of a number. Ends up the fastest one was the one that took the fewest number of times through a for loop. The final code along with the two previous tries are below.
I used wikipedia to find several different algorithms for calculating Euler’s totient.
def isprime(n):
if n == 0 or n == 1: return False
for i in range(2, int(n**0.5 + 1)):
if n%i == 0: return False
return True
primes = []
for n in range(10**6):
if isprime(n) == True:
primes.append(n)
def phi(n):
pfact = []
answer = float(n)
if isprime(n) == True: pfact.append(n)
for p in primes:
if p > (n**.5 + 1):
for f in pfact:
answer = answer * (1 - (1/float(f)))
return answer
elif n%p == 0:
pfact.append(p)
phis = [[0]]
for n in range(1, 10**6 +1):
phis.append([float(n/phi(n)), n])
print max(phis)
def phi(n):
if n == 1: return 1
count = 0
for k in range(1, n):
for i in range(2, k+1):
if (k%i == 0) and (n%i == 0):
break
else:
count += 1
return count
maximum = [0, 0]
for n in range(1, 10**6 + 1):
if n%1000 == 0: print n
if float(n / phi(n)) > maximum[0]:
maximum = [float(n / phi(n)), n]
print maximum
def gcd(n, k):
if n%k == 0: return k
else: return gcd(k, n%k)
def phi(n):
count = 0
for k in range(1, n+1):
if gcd(n, k) == 1:
count += 1
return count
phis = [[0]]
for n in range(10**6, 1, -1):
print n, max(phis)
phis.append([float(n/phi(n)), n])
print max(phis)