백준알고리즘 #2609 최대공약수와 최소공배수 Java

백준알고리즘 #2609 최대공약수와 최소공배수 문제

최대공약수와 최소공배수 코드

먼저 두 수를 비교하여 큰수와 작은수를 나눈다.

나눈 이유는 for문에서 작은수 까지만 반복하면 되기 때문에 일부러 큰수와 작은수를 정하는 구문을 넣었다.

for문에서는 최대공약수를 찾기 위해 1부터 두 수중 작은 수까지 반복하면서 큰수를 i로 나누었을때, 그리고 작은 수를 i로 나누었을 때 모두 나머지가 0이 되는 수(공약수)를 찾아 gcd변수에 넣는다. for문을 빠져나왔을 때 gcd의 값은 공약수 중 가장 큰 최대공약수가 된다.

 

두번째 while문에서는 최소공배수를 구한다.

먼저 차례로 증가할 수 j를 만든 후 lcm(최소공배수)가 0인 동안 반복하도록 한다.

위와 마찬가지로 이번에는 j를 큰 수로 나누었을때, j를 작은 수로 나누었을 때 나머지가 모두 0이 되는 j값을 찾는다. 가장 작은 j값을 찾게되면 lcm == 0 이 아니게 되기 때문에 while문을 빠져나가고 자연스럽게 lcm에는 최소공배수가 담긴다. (break문은 빼도 무방하다)