오일러 피함수1 오일러 피 함수(Euler's phi function) Euler's phi function 오일러 피(파이) 함수 $\phi (n)$ 란 1과 n까지의 정수 중 n과 서로소인 개수를 뜻한다. 거부감 없이 정의는 매우 쉽다. int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); } int getEulerPhiFunc(int n){ int cnt = 0; for(int i = 1; i < n; i++){ if(gcd(n, i) == 1) cnt++; } return cnt; } 대충 예외 생각 안 하고 구현하면 위와 같이 구하면 된다. 이 방법은 $ \phi (n) $ 의 성질을 하나도 안 따져보고 구했으니, 더 좋은 방법을 위해 성질을 알아보자. 일단 가장 간단하게 유추할 수 있는 것이 있다. $$ \phi(p).. 2019. 10. 17. 이전 1 다음
