C++ 유클리드 호제법

유클리드 호제법 ( 알고리즘 중에 하나 )

A    B    Rest

152 68 20

68 20 8

20 8 4

8 4 

그러면 4가 된다 최대 공약수

최소 공배수는 

A = a * GCD

B = b * GCD

LCM = ab GCD

#include <iostream>

#include <vector>

using namespace std;

int main() {

int a,b;

int A,B;

cin >> a >> b;

int GCD,LCM;

A = a;

B = b;

while(1)

{

int r = a % b;

if( r == 0)

{

GCD = b;

break;

}

a = b;

b = r;

}

cout << GCD << endl;

LCM = (A/GCD) * (B/GCD) * GCD;

cout<< LCM << endl;

return 0;

}

증명: