[백준] 2609 최대공약수와 최소공배수

문제 : 두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 프로그램을 작성하시오.

최대공약수와 최소공배수를 출력하는 문제입니다.

최대공약수의 정의는 두 수를 나누어 나머지가 0이 되게 하는 수 중 가장 큰 수이고,

최소공배수는 두 수의 공통의 배수 중 가장 작은 수를 의미합니다.

저는 유클리드 호제법이라는 알고리즘을 사용할 것 입니다.

예를 들어 12와 40의 최대공약수를 구한다면,

40%12=4  //피연산자와 나머지를 

12%4=0   //연산자와 피연산자로 이동해줍니다. 그리고 0이 될때까지 이 과정을 반복합니다.

나머지가 0이 될 때, 그 때의 피연산자가 최대공약수 입니다.

그럼 최소공배수는 어떻게 구할까요? 간단합니다. 두 수의 곱/최대공약수 입니다.

이걸 이용하면 계산을 반복할 필요도 없고 연산 시간도 줄어듭니다.

#include <stdio.h>  /* 유클리드 호제법 알고리즘 사용*/  
 
int main()
{
    int num,k,j=0; 
    int arr[100000];    
    
 
    scanf("%d %d",&arr[0],&arr[1]);
    if(arr[0]<arr[1])   //맨 왼쪽에 더 큰 수 입력   
    {
        k=arr[1]; arr[1]=arr[0]; arr[0]=k;
    }
    while(1)  //오른쪽으로 가면서 나머지 입력  
    {
        arr[j+2]=arr[j]%arr[j+1]; 
        if(arr[j+2]==0)
        {
            break;
        }
        j++; 
    }
    printf("%d\n%d",arr[j+1],arr[0]*(arr[1]/arr[j+1]));     
}