Euler's phi (Totient function)

1 과 n 사이의 수 중 (1포함) n 과 서로소(co-prime) 인 수는 몇개?

여기서 p 는 n 을 나누어떨어뜨리는 prime 이다.

예를들어 n = 10 이라고 하면, p = { 2, 5 }

phi(10) = 10 * (1-1/2) * (1-1/5) = 10 * 1/2 * 4/5 = 4

실제로 10 과 서로소인 수는 1, 3, 5, 7

예전엔 원리를 알았는데.. 기억이 안난다.. -_-;;

신기하구먼~