オイラーのφ関数を、RubyのPrimeモジュールを使って素朴に実装したものです

phi.rb

require 'prime'

def φ(n)
  if n == 1
    return 1
  end
  Prime.each(n-1) do |p|
    if n % p == 0
      b = n
      j = 0
      while b % p == 0
        b /= p
        j += 1
      end
      return p ** (j-1) * (p-1) * φ(b)
    end
  end
  return n-1
end

(1..20).each do |n|
  print "#{φ(n)}, "
end
puts