Euler totient function 썸네일형 리스트형 [오일러 Phi 함수] Euler totient function 오일러 Phi 함수 $\phi(n)$ 는 1부터 n까지 사이의 수 중에서 n과의 최대공약수가 1인 수의 갯수를 나타내는 함수이다. Phi 함수는 아래와 같은 성질을 만족한다. 1) 만약 p가 소수라면 $\phi(p)$ = p-1 를 만족한다. 2) 만약 p가 소수이고, k$\geq1$라면 1부터 $p^k$까지 정확히 $p^k/p$가 p로 나누어지기 때문에 다음을 만족한다. $\phi(p^k) = p^k - p^{k-1}$ 3) a와 b가 서로소라면 다음을 만족한다. $\phi(ab) = \phi(a) * \phi(b)$ 이를 바탕으로 수식을 정리하면, 아래와 같다. $\phi(n)$ = n * $(1- \frac{1}{p_1})$* $(1- \frac{1}{p_2})$* $(1- \frac{1}{p_3}.. 더보기 이전 1 다음
