C++ 최대공약수, 최소공배수 구하는 로직

 

두 자연수의 곱 = 최대공약수 x 최소공배수

 

최대공약수, 최소공배수 둘 다 구해야하는 상황에서

위 공식을 이용하면,

더 빠르게 결과를 얻을 수 있다.

 

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    // 임의의 두 자연수가 주어졌을 때,
    // 작은 수, 큰 수를 일단 구분한다
    int small, big;
    
    if( n > m ){
        big = n;
        small = m;
    }else{
        big = m;
        small = n;
    }
    
    
    // 최대공약수를 구한다
    // 두 자연수의 공통공약수 1로 초기화
    int greatestCommonFactor = 1;
    
    // 최대공약수는 작은 수보다 클 수 없으므로
    // 작은 수 부터 2까지 loop로 살펴보면서,
    // 주어진 두 자연수를 나눴을 때 나머지가 없는 경우가 나타나면
    // 최대공약수를 찾은 것이고 loop 를 빠져나온다.
    for(int i=small ; i>=2 ; i--){
        if( small % i == 0 && big % i == 0){
            greatestCommonFactor = i;
            break;
        }
    }
    
    // 최소공배수르 구한다
    // 주어진 두 자연수의 곱에서 앞서 구한 최대공약수를 나눠주면 끝
    LeastCommonMultiple = small * big / greatestCommonFactor;



	// 답을 세팅해 준다
    answer.push_back(greatestCommonFactor);
    answer.push_back(LeastCommonMultiple);
    
    return answer;
}

 

 

 

 

최대공약수 없이, 최소공배수만 구해야 하는 경우는

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    // 임의의 두 자연수가 주어졌을 때,
    // 작은 수, 큰 수를 일단 구분한다
    int small, big;
    
    if( n > m ){
        big = n;
        small = m;
    }else{
        big = m;
        small = n;
    }
    
    
    // 최소공배수
    // 주어진 두 자연수 중, 큰 수로 초기화
    int LeastCommonMultiple = big;
    
    // 큰 수의 배수를 살펴본다
    // 큰 수에서 (큰 수 * 작은 수) 까지 loop로 살펴보면 된다
    for( int j=1 ; j <= small ; j++){
        if( (big * j) % small == 0 ){
            LeastCommonMultiple = big * j;
            break;
        }
    }
    
    

	// 답을 세팅해 준다
    answer.push_back(greatestCommonFactor);
    answer.push_back(LeastCommonMultiple);
    
    return answer;
}