n/φ(n)이 최소가 되며 두 값이 순열관계인 천만 이하의 n은?
앞의 문제와 유사하지만, 한 번 더 꼬아 난이도가 살짝 올라간 문제. 사실, 이 문제를 풀기 위해 좀 더 공부를 하고 앞의 포스팅을 수정했다. \( \phi (n) \) 함수를 오일러가 정리한 대로 제대로 구현하지 않아도 앞의 문제는 풀 수 있었지만, 이 문제는 아니다. 일단 천만이라는 수도 무시무시한데다, 그 뒤에 \( n \)과 \( \phi (n) \)이 순열인지 여부까지 확인해야 된다. 코드의 기본은 앞의 내용을 (대폭 수정한 뒤에) 거의 그대로 가져왔다. 에라토스테네스의 체를 활용해서 소인수 테이블을 먼저 만드는 것도 동일하다. 순열(permutation) 여부를 확인하는 코드와 아주 약간 바뀐 규칙 외엔 거의 동일하다. #include #include using namespace std; #i..