Euclidean algorithm (유클리드 호제법)

두 자연수 a,b 의 GCD(Great Common Divisor)인 d를 기호로 (a,b)로 나타내면 d=(a,b)이다.
a,b는 모두 GCD인 d로 나누어 떨어지므로 a-b도 d로 나누어 떨어진다.
※ d는 a-b와 b의 GCD이다.
 이와 같은 과정을 반복하여 두 수의 GCD를 구하는 방법이 Euclidean algorithm!! 

#include <iostream>

using namespace std;

int main(void)

{

int i,j,GCD;

cout << "Input the 1st number : ";

cin >> i;

cout << "\nInput the 2nd number : ";

cin >> j;

while(1)

{

if(i==j)

{

GCD = i;

cout << "\n\n GCD : " << GCD << endl;

break;

}

if(i>j)

i=i-j;

else

j=j-i;

}

}