Study Record

1. 약수(Divisors) 24의 양의 약수 = 1, 2, 3, 4, 6, 8, 12, 24 어떤 수를 나누었을 때 나머지가 0이 되는 수이다. + 모든 자연수는 1과 자기 자신을 약수로 갖는다. + 'a는 b의 약수이다'를 a|b라고 표현하기도 한다. 2. 공약수(Common Divisor) a,b 가 정수일 때 d|a 이고 d|b 이면 d 는 a와 b의 Common Divisor(공약수) 이다. 3. 최대 공약수 - GCD (Greatest Common Divisor) d > 0 이고, d가 a와 b의 공약수들 중 가장 큰 수면, d 는 a와 b의 gcd(최대공약수)이다. + gcd(a,b) : a와 b의 최대공약수 + 공약수는 최대공약수를 나눌 수 있다. d' : a와 b의 공약수 d : a와 b..

유클리드 알고리즘(EA)은 GCD(최대공약수)를 구해주는 알고리즘이다. GCD 알고리즘은 다음과 같다. // input : a , b > 0 // output : gcd(a,b) - a 와 b 의 최대공약수 R0