[Bronze 1] 2609번 최대공약수와 최소공배수

최대공약수를 구하는 방법은 아래와 같다.

n1과 n2를 동시에 나눠줄 수 없을 때 까지 계속 나눠주는 방식을 사용한다.

이때 프로그래밍 언어 특성 상 계속 나눠주는 방식 보단 n1과 n2 중 작은 수부터 나눠 떨어지는 수를

최대 공약수로 사용해야한다.

 

최소공배수는 (n1 / 최대 공약수) * (n2 / 최대 공약수) * 최대공약수 를 사용하면 구할 수 있다.

이러한 공식의 근거는 최대 공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수이기 때문이다.

 

#include <iostream>
using namespace std;

int main(){
    int n1,n2;
    cin>>n1>>n2;
    unsigned long max, min;
    int t = 0;
    if(n1>n2) t = n2;
    else t = n1;
    for(int i =t;i>0;i--){
        if(n1%i==0&&n2%i==0){
            max = i;  
            break;
        } 
    }
    min = (n1/max) * (n2/max) * max;
    
    cout << max <<'\n';
    cout << min <<'\n';
}