[C] 유클리드 호제법

 정의

• 두 정수 m,n(m > 0)이 있을 때, m과 n의 최대공약수는 m-n과 n의 최대공약수와 같다.

C 로 아래와 같이 표현할수 있다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int euclidean(void)
{
	int a,b,m,n;
 
	printf("Input 2 integer value : ");
	scanf("%d %d", &a, &b);
 
	m=a, n=b;
 
	while(m != n) {
		if(m>n) {
			m = m-n;
		}
		else {
			n = n-m;
		}
	}
 
	printf("GCM is %d\n", m);
 
	return 0;
}
 
int main()
{
	euclidean();
	return 0;
}