[Algorithm] 최대공약수, 최소공배수 구하기

입력받은 두수의 최대공약수와 최소공배수를 구하기

최대공약수와 최소공배수를 구할 두 수 중 큰수와 작은수를 정한 뒤 큰 수를 작은수로 나누어 나머지를 구합니다. 이때 나머지가 0이면 그때의 작은수가 최대공약수이고, 원래의 두수를 곱한 값을 최대공약수로 나눈 값이 최소공배수입니다. 만약 큰수를 작은수로 나누었을 때, 나머지가 0이 아니면, 그떄의 작은 수를 큰수로 하고 나머지를 작은수로 하여 나머지가 0이 될때까지 반복합니다.

 

더 빠른 최대공약수 구하는 유클리드 호제법이 궁금하시다면 아래 글을 참고해주세요.

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기

 

C언어 / C++ 코드

#include<stdio.h>
main()
{
	int a,b,big,small,mok,nmg,gcm,lcm;
	scanf("%d %d",&a,&b);
	if(a>=b){
		big = a;
		small = b;
	}else{
		small = a;
		big = b;
	}
	
	while(1){
		mok = big/small;
		nmg = big-mok*small;
		if(nmg==0){
			gcm = small;
			lcm = a*b  / gcm;
			printf("최대공약수 = %d \n최소공배수 = %d",gcm,lcm);
			break;
		}
		
		big = small;
		small = nmg;
	}
}

결과

 

댓글

Designed by JB FACTORY