# 069 : トーティエント関数の最大値

オイラーのトーティエント関数$$φ(n)$$(ファイ関数とも呼ばれる) とは,$$n$$未満の正の整数で$$n$$と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,$$φ(9) = 6$$となる.

| $$n$$ | 互いに素な数      | $$φ(n)$$ | $$n/φ(n)$$ |
| ----- | ----------- | -------- | ---------- |
| 2     | 1           | 1        | 2          |
| 3     | 1,2         | 2        | 1.5        |
| 4     | 1,3         | 2        | 2          |
| 5     | 1,2,3,4     | 4        | 1.25       |
| 6     | 1,5         | 2        | 3          |
| 7     | 1,2,3,4,5,6 | 6        | 1.1666...  |
| 8     | 1,3,5,7     | 4        | 2          |
| 9     | 1,2,4,5,7,8 | 6        | 1.5        |
| 10    | 1,3,7,9     | 4        | 2.5        |

$$n ≤ 10$$では$$n/φ(n)$$の最大値は$$n=6$$であることがわかる.

$$n ≤ 1,000,000$$で$$n/φ(n)$$が最大となる値を見つけよ.
