オイラーのトーシェント関数
与えられた数
n に対して、オイラーのトーシェント関数の結果を求めます。オイラーのトーシェント関数 (Euler’s totient function) は、1 から
n までの整数のうち、n と互いに素である（最大公約数が 1 の）数がいくつあるかを求めるものです。
入力
入力は単一の整数
n (1 ≤ n ≤ ) から構成されます。出力
プログラムは
n に対するオイラーのトーシェント関数の結果を出力してください。例
入力 | 出力 |
20 | 8 |
9 | 6 |
解説
- 20 → 1, 3, 7, 9, 11, 13, 17, 19
- 9 → 1, 2, 4, 5, 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB