최대 공약수, 최소 공배수 알고리즘 파악하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를  활용한 알고리즘입니다.

ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8

라고 한다..... c언어로 알고리즘을 파악해보자. (C프밍 과제)

 

먼저 최소 공약수 알고리즘이다.

1. 두 수를 입력 받는다.
2. 두 수중 큰 수를 x, 작은 수를 y라고 한다.
3. y=0이면 최대공약수는 x이며 프로그램을 종료한다.
4. r = x % y
5. x = y
6 y = r
7. 다시 3번으로 돌아간다. 

#include <stdio.h>

int main() {
	int x, y, tmp, r = 0;
	printf("두 개의 정수를 입력하시오: ");
	scanf_s("%d %d", &x, &y);

	if (x < y) {
		tmp = x;
		x = y;
		x = tmp;
	}// x를 무조건 큰수로 만들기, y에 작은 수를 넣어주기.

	while(y != 0){
		r = x % y; 
		x = y;
		y = r; //작은 수인 y를 x에 x와 y를 나눈 나머지를 r에다 넣어주고 y가 0이 될때 까지 계산
	}
	printf("%d", x);
}

 

최소 공배수 알고리즘이다. 최소공배수를 구하고 x * y / GCD를 해주면 된다

#include <stdio.h>

int main() {
	int x, y, tmp, r = 0;
	printf("두 개의 정수를 입력하시오: ");
	scanf_s("%d %d", &x, &y);
	int a = x, b = y;
	if (x < y) {
		tmp = x;
		x = y;
		x = tmp;
	}// x를 무조건 큰수로 만들기

	while(y != 0){
		r = x % y;
		x = y;
		y = r;
	}
	printf("%d", a * b / x);//a*b / x y의 최대 공약수
}