[정보통신기술용어해설] | 메뉴 닫기 |
GCD, LCM Common Divisor, Greatest Common Divisor, Least Common Multipler 공약수, 최대공약수, 최소공배수 | (2013-11-07) |
1. 공약수(Common Divisor) ㅇ 여러 정수를 동시에 나눌 수 있는 정수 2. 최대 공약수 (Greatest Common Divisor) : gcd(a,b) = d ㅇ 공약수 중 가장 큰 정수 ㅇ 최대공약수 gcd(a,b) = d 조건 - d ≥ 1 . 최대공약수는 양의 정수 - d | a, d | b . 최대공약수는 a,b의 공약수 - k | a 이고 k | b 이면, k | d . a,b의 모든 공약수는 또한 최대공약수의 약수가 됨 ㅇ 성질 - gcd(a,0) = a 는 항상 성립 . 0 이 아닌 모든 정수는 0 을 나눌 수 있으므로 - 서로소 : 공통 인수를 갖지 않는 수 . gcd(a,b) = 1 이면, a 및 b 는 서로소 3. 최소 공배수 (Least Common Multipler) : lcm(a,b) ㅇ 모두의 배수가 되는 최소의 자연수
[소수,최대공약수] | 1. 소수, 합성수 2. 최대공약수 3. 소인수 분해 |