유클리드 호제법 c언어 구현하기

<개념>

두 정수의 최대 공약수를 구하는 알고리즘

<방법>

1.  두 수 중에서 큰 수를 a, 작은 수를 b라고 하고 a를 b로 나눈다.
2. a가 b로 나누어떨어지면 두 수의 최대공약수는 b이다.
3. a가 b로 나누어떨어지지 않으면 a를 b로 나눈 나머지와 b에 대하여 1번부터 다시 반복한다.

#include <stdio.h>

int	Euclidean(int a, int b)
{
	if (b == 0)
		return (a);
	else
		return (Euclidean(b, a%b));
}

int	main()
{
	int	a = 10;
	int	b = 4;

	printf("%d", Euclidean(10, 4));
	return (0);
}

10과 4 의 최대 공약수 = 2 가 출력된다.

 

<최소공배수구하는 방법>

 

위의 방법으로 최대 공약수를 구하면 

 

최소공배수 = (a * b) / 최대공약수