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



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

신기하구먼~




'Problem Solving > Algorithm notes' 카테고리의 다른 글

Euler's phi (Totient function)  (0) 2016.08.15
Inversion Count  (0) 2016.01.31
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23

Leave a Comment


to Top