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