RSS Feed

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)는 언제 최대가 됩니까?


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.