두 개의 수 A와 B의 최대공약수를 D라 하면, 세 개의 수 A, B, C의 최대공약수는 D와 C의 최대공약수와 같다.

이런 규칙을 이용하면 두 수의 최대공약수를 구하는 함수 한 개만으로도 여러 수의 최대공약수를 구할 수 있다.

최소공배수 역시 두 수의 최소공배수를 구해 나가는 방법으로 구할 수 있다.

a배열에 N개의 수가 저장되어 있다고 가정한다면 다음과 같이 구현할 수 있다.

코드

gcd = lcm = a[0];
for (i=1; i < N; i++) { 
    gcd = gcd_get(gcd, a[i]); 
    lcm = lcm / gcd_get(lcm, a[i]) * a[i];
}

코드분석

첫 번째 수를 최대공약수(gcd)로 정하고 두 번째 수부터 이전까지의 최대공약수(gcd)와 현재 배열의 값(a[i])의 최대공약수를 구하여 다시 gcd에 저장한다.

이러한 작업을 마지막까지 반복하면 모든 수의 최대공약수가 구해진다.

최소공배수도 같은 방법으로 구할 수 있다.

GCD, LCM timer 1s memory 64MB

GCD, LCM 1s 64MB