[ 수학 ] 최대공약수와 최소공배수 연습하기 JAVA

 

문제

 

 

 

 

 

풀이

 

 

최소공배수, 최대공약수를 구하는 연습을 백준 2609번 문제를 통해 연습해보도록 하겠습니다.

문제 풀이는 유클리드 호제법을 이용하였습니다.

 

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 나무위키

 

간단히 보면 a와 b 두 수에 대하여 유클리드 호제법을 사용한다고 하면

a를 b로 나눈 나머지를 N 이라고 했을 때

a와 b의 최대공약수는 --> b와 N 의 최대공약수와 같게 된다는 설명입니다. 

                    GCD ( a, b ) ==  GCD ( b, N )

 

이해 하기 쉽게 두 수 a, b  를 20과 12로 잡아보겠습니다.

       a 를 b로 나눈 나머지 8을 N 으로 둔다면  a = 12 , b = 8이 됩니다.

계속해서 이는 곧   a = 8  ( 이전의 b ) ,   b =  4 ( 12를 8로 나눈 나머지 )

마지막으로 a = 4, b = 0 이 되고 ,      b가 0이 될 때의 a값 ( = 4 ) 이 두 수의 최대 공약수입니다.

 

            GCD ( 20 , 12 )  ==>  GCD ( 12 , 8 )    ==>   GCD (  8 ,  4 )   ==>    GCD ( 4,  0 )

※ 20과 12의 최대 공약수는 4가 됩니다.

 

코드에서는 반복되는 이 과정을 while 반복문으로 처리해주었습니다.

초기값 a와 b를 최소공배수를 구할 때 다시 사용하기 위해서 GCD 연산과정은 c와 d를 이용하였습니다.

여기에서 d가 0이 될 때의 c 값을 이용하여 최대 공약수를 구해주었고

 

 

최소공배수는 a와 b 각각의 수를 최대공약수인 c로 나눈 뒤에 곱해주면 됩니다.

                    4 *  ( 20 / 4 )  *  ( 12 / 4  ) ==>   4  *  5  *  3   =  60

 

 

 

코드

 

 

 

 

출처

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수