본문 바로가기

Discrete Math/Number theory

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;
}
}


 

'Discrete Math > Number theory' 카테고리의 다른 글

소수판별법  (0) 2011.10.06
Sieve of Erathosthenes(에라토스테네스의 체)  (2) 2011.10.05