Euler's Totient Function

Ruby

Euler's phi function: number of coprimes of an integer m
phi(m) = m*Prod(1-1/p) [where p: prime number and p|m]

def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

a test of multiplicative law

[9,25,225].map{|m|p phi(m)}
6
20
120

Hence, phi(9)*phi(25) == phi(9*25)

Fint challenge

p phi(10000)
4000

p (2**4 - 2**3)*(5**4 - 5**3)
4000

Silverman's "A Friendly Introduction To Number Theory" has an excercise 11.3 p.76 to find phi(1000000) - Answer: inductively that must be 400000; however, Ruby needs more power to run.