[알고리즘] 최대공약수, 최소공배수 구하기.

최대공약수는 어떠한 두수의 공약수중 가장 큰값 GCD라고 표현한다.

가장 중요한 팁.. 

예를 들어서 48의 약수를 구한다고 가정해보자.

48은 1 * 48 ,  2 * 24 , 3 * 16 , 4 * 12  , 6 * 8 

     8 * 6 ,  12 * 4 , 16 * 3 , 24 * 2 , 48 * 1

 

여기서 중요한점은 6 * 8 을 기준으로 그 뒤에 곱셈은 앞에서 나온 수들의 반복이다.

그래서 48의 약수를 구하는 루프를 돌릴때는 1부터 48 까지 모든 정수를 나누어 떨어지는가 아닌가를 판단할 필요없이

48의 제곱근 값까지만 루프를 돌면된다. 즉 1부터 6 까지만 돌면 된다.

21번 라인의 조건문을 잘 보기 바란다.

sum 에 계속 곱해져 가는 값은 흔히 우리가 최대공약수를 구하기 위해 서로 같이 나누어 떨어지는 수를 찾는부분이다.

결국 입력된 값이 서로소 관계가 될때까지 구하게 되며 루프를 빠져나왔을때 sum의 값에는 최대공약수가 들어가게 된다.

여기서 또 나아갈수 있는 부분은 

이미 두 입력값 m 과 n 은 서로소의 값이 들어있기 때문에 sum 에 m과 n을 둘다 곱하면

최소공배수까지 한번에 구할수 있다.

 

#include <stdio.h>    
  
#include <math.h>    
    
int main(void)    
{    
    int m,n;     
  
    int i;    
  
    int sum=1;    
  
    printf("두 수 입력 : ");    
  
    scanf("%d %d",&m,&n);    
  
    if ( m == n)    
        sum = m;    
    else    
  
        for(i=2;i<=sqrt((double)m) && i<=sqrt((double)n);i++)   
       
            if(m%i==0 && n%i==0){    
  
                sum *= i;    
                m /=i;    
                n /=i;    
                i--;    
            }    
  
    printf("  GCD  : %d\n", sum);    
  
    printf("  LCM  : %d\n", sum * m * n);  
    
}