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' 카테고리의 다른 글

Inversion Count  (0) 2016.01.31
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
점과 선분과의 거리  (2) 2011.01.22
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12

to Top