Skip to content

Instantly share code, notes, and snippets.

@hyuki0000
Created Jul 2, 2017
Embed
What would you like to do?
オイラーのφ関数を、RubyのPrimeモジュールを使って素朴に実装したものです
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
@hyuki0000
Copy link
Author

hyuki0000 commented Jul 2, 2017

20170702215525

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment