最大公約数(ユークリッドの互除法)
gcd = lambda m, n: n and gcd(n, m % n) or m
オイラーのφ関数
eulerphi = lambda n: sum(int(gcd(m + 1, n) == 1) for m in range(n))
テスト
>>> [eulerphi(n+1) for n in range(16)]
[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8]
More than 1 year has passed since last update.
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme