GCD & LCM
유클리드 호제법
최대공약수와 최소공배수를 구할 두 수 중 큰 수와 작은 수를 정한 뒤
작은 수로 큰 수를 나누어 나머지를 구한다.
if ( 나머지 == 0 )
그때의 작은 수가 [최대공약수]이고,
원래 두 수를 곱한 값을 최대공약수로 나눈 값이 [최소공배수]이다.
else
큰 수 = 작은 수
작은 수 = 나머지
나머지가 0이 될 때까지 반복
[1] GCD & LCM Code
#include<iostream>
using namespace std;
pair<int,int> gcdAndlcm(int a, int b){
int big, small;
int mok, nmg, gcd, lcm;
if ( a >= b){
big = a;
small = b;
}
else{
big = b;
small = a;
}
while (1) {
mok = big / small;
nmg = big - mok * small;
if (nmg == 0){
gcd = small;
lcm = a * b / gcd;
return make_pair(gcd, lcm);
}
big = small;
small = nmg;
}
}
int main(){
int a,b;
cin >> a >> b;
pair<int, int> p;
p = gcdAndlcm(a, b);
cout << "gcd : " << p.first << endl;
cout << "lcm : " << p.second << endl;
return 0;
}
[2] GCD & LCM Code
int gcd(int a,int b){ //반복문을 이용한 방법
int mod = a % b;
while(mod > 0)
{
a = b;
b = mod;
mod = a % b;
}
return b;
}
int gcd(int a,int b){ //재귀 함수형
if( a % b == 0 )
return b;
else
return gcd(b, a % b);
}
int gcd(int a, int b){ //삼항 연산자 축약형
return (a % b == 0 ? b : gcd(b,a%b));
}
lcm = a * b / gcd;
[3] GCD & LCM Code
void gcdlcm(int a,int b){
if(a > b){
swap(a,b);
}
for(int i = a; i > 0; i--){
if(((a%i) == 0) && ((b%i) == 0)){
printf("GCD : %d \n", i );
printf("LCM : %d \n", (a*b)/i);
break;
}
}
}