연습문제 > N개의 최소공배수

두수의 최대 공약수를 구하면 

최소 공배수를 알 수 있다인데

 

수학적이기도하고 자력으로는 못풀어냈다

고대 그리스 수학자 유클리드가 제시한 유클리드 호제법을 이용한 풀이인데

호제법이란 서로를 나누는 방법이라는 뜻이다

유클리드 호제법을 이용해서 최대공약수를 구하고

최대공약수로 최소 공배수를 구한다

 

설명

1. 유클리드 호제법을 사용한 최대공약수 구하기:
   • gcd 함수는 두 수 a와 b의 최대공약수를 유클리드 호제법을 사용하여 구합니다.
   • while (b !== 0) 루프를 통해 b가 0이 될 때까지 a % b의 값을 b에 대입하고, a는 b로 대체합니다.
   • b가 0이 되면 a가 두 수의 최대공약수가 됩니다.
2. 최소공배수 구하기:
   • lcm 함수는 두 수 a와 b의 최소공배수를 (a * b) / gcd(a, b)로 계산합니다.
   • 최대공약수를 구한 후, 이를 두 수의 곱에 나누면 최소공배수를 얻을 수 있습니다.
3. 배열의 최소공배수 구하기:
   • solution 함수는 배열 arr의 첫 번째 원소로 result를 초기화합니다.
   • for 루프를 통해 배열의 두 번째 원소부터 마지막 원소까지 순회하면서 현재의 result와 배열의 현재 원소(arr[i])의 최소공배수를 계산하여 result에 저장합니다.
   • 루프가 끝나면 result에는 배열 전체의 최소공배수가 저장됩니다.

유클리드 호제법을 사용하면 효율적으로 두 수의 최대공약수를 구할 수 있으며, 이를 바탕으로 여러 수의 최소공배수를 구하는 문제도 쉽게 해결할 수 있습니다.