n/φ(n)이 최대가 되는 1백만 이하의 n 찾기
Problem 69
출제 일시 : 2012-02-04 18:21:52, ☕ ☕
오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 수의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(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)는 언제 최대가 됩니까?