황소개발자

이걸 아직도 파악하지 못하고 있었다니.. 반성한다. 유클리드 호제법은 기원전 300년에 나온 첫번째 알고리즘으로 유명하다. a 를 b로 나눈 나머지를 r 이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수이다. 다시말해서, a와 b의 최대공약수는 b와 a%b의 최대공약수이다. 재귀가 느껴지는가? 반복이 느껴지는가? a%b 값이 0이 되었을 때, b 값이 최대공약수이다. 최소공배수는 어떻게 구할까? 최대 공약수를 G라고 했을 때, a = G * x b= G * y 이다. G가 최대공약수 그 자체이기에, x, y는 서로소이다. 하튼, a * b = G * G * x * y 이다. 그럼 최소공배수는 a * b / G 이다. 놀랍지 않은가? gcd = greatest common divisior : ..