n/φ(n)이 최대가 되는 백만 이하의 n은?
그간 도저히 포스팅할 시간이 나지 않았다. 정말이지 오랜만의 포스팅. 오랜만에 오일러 프로젝트를 하나 풀어봤다. 오일러의 \( \phi(n) \) 함수는 주어진 숫자보다 작은 수 중에 서로소인 수의 개수이다. 수학 쪽 분들께는 아래와 같이 정의될 수 있다고 한다. \( \phi(n) = n {\prod _{p|n}^{}} \left (1- \frac{1}{p} \right ) \) 그리고, 저 정의를 활용하면 \( n / \phi(n) \)가 최대가 되는 경우를 좀 더 손쉽게 알 수 있다고 한다. 그런데, 저 식을 제대로 이해하지 못하면서 코드를 만들고 싶지는 않아서 그냥 정공법으로 풀어보기로 했다. 첫번째 시도 모든 것을 무식하게 돌려보기로 했다. 백만 이하의 모든 수 각각에 대해 그 이하의 모든 수들..