c++ 최대공약수, 최소공약수 구하기

-최대공약수 구하기

유클리드 호제법으로 

• a,b : 최대공약수를 구하고자 하는 두 수
• r : a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
• 식 : gcd(a,b) = gcd(b,r)

구할 수 있다.

이때 a와 b의 관계는 항상 a>b여야 하므로 if(a<b)일 경우 swap(a,b)를 통해 a가 항상 크도록 하자

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

 

-최소공약수 구하기

int lcm(int a, int b){
    return a * b / gcd(a,b);
}

 

-ex) 18, 45의 최대/최소공약수 구하기

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int gcd(int a, int b){
    int temp;
    while(b!=0){
        temp=a%b;
        a=b;
        b=temp;
    }
    return a;
}
int lcm(int a, int b,int gcd_result){
    return (a*b)/gcd_result;
}
int main() {
    vector<int> answer;
    int gcd_result;
    int n=18;
    int m=45;
    
    if(n>m){
        gcd_result=gcd(n,m);
        answer.push_back(gcd_result);
        answer.push_back(lcm(n,m,gcd_result));
    }
    else{
        gcd_result=gcd(m,n);
        answer.push_back(gcd_result);
        answer.push_back(lcm(m,n,gcd_result));
        
    }
    
    cout<<answer[0]<<endl;
    cout<<answer[1]<<endl;

        return 0;
    }

result