들어가며처음으로 수학과 관련된 알고리즘을 다뤄보게 되었습니다. 사실 정확히 말하자면 오일러 피 함수는 알고리즘이라기보단 정수론에서 배우는 수학 개념입니다. 의미는 단순하지만 증명은 어렵고 복잡하기 때문에 함수를 외운 뒤 구현하는 법만 이해하면 충분합니다. 오일러 피 함수 : Euler Phi Function1. 정의오일러 피 함수는 자연수 n이 주어졌을 때 n 이하의 자연수 중에 n과 서로소인 수의 개수를 구하는 데 사용됩니다. 2. 표기$$\Large \phi(n)$$함수의 표기는 위와 같고 피(phi)라고 읽습니다. $\phi(6)$이라면 6 이하의 자연수 중 6과 서로소인 자연수는 1, 5가 있으므로 2를 값으로 가집니다. 3. 수식$$\large\phi(x)=n\prod_{p|n}(1-\frac..
