최대공약수(GCD)와 최소공배수(LCM) 구하기

아래의 개념을 잘 생각하면 구현할 수 있다.

최소공배수(Least Common Multiple)
만약 A가 B와 C의 최소공배수라면, A는 B로 나누었을 때도 나누어 떨어지고, C로나누었을 때도 나누어 떨어지는 수중에 가장 작은 수이다.

최대공약수(Greatest Common Divisor)
만약 A가 B와 C의 최대공약수라면, A는 B와 C를 각각 A로 나누었을 때, 나누어 떨어지는 수중에서 가장 큰 수이다.

#include <stdio.h>

int getLCM(int num1, int num2);	//최소공배수(Least Common Multiple)를 리턴하는 함수
int getGCD(int num1, int num2); //최대공약수(Greatest Common Divisor)를 리턴하는 함수


int main(void)
{
	int num1, num2;
	
	printf("두 정수를 입력하세요 : ");
	scanf("%d %d", &num1, &num2);
	printf("최소공배수: %d\n최대공약수: %d\n", getLCM(num1, num2), getGCD(num1, num2));
		
	return 0;
}

//두 수 num1과 num2를 입력받아 최대공약수를 리턴
int getGCD(int num1, int num2)
{
	int GCD=0;
	if(num1 != 0 && num2 != 0)	//입력받은 두 수가 모두 0이 아닌경우에만 실행
		//입력받은 두 수중 한 수를 GCD에 넣고 1씩 감소시키면서 
		//num1과 num2가 모두 GCD로 나누어 떨어질 때(나머지=0) 멈춘다.
		for(GCD=num1; num1%GCD || num2%GCD;GCD--);
	return GCD;
}

int getLCM(int num1, int num2)
{	
	int LCM=0;
	if(num1 !=0 && num2 != 0)	//입력받은 두 수가 모두 0이 아닌경우에만 실행
		//입력받은 두 수 중 한 수를 LCM에 넣고 1씩 증가시키면서 
		//LCM을 num1과 num2로 각각 나누었을 때 나누어 떨어지면 멈춘다.
		for(LCM=num1; LCM%num1 || LCM%num2;LCM++);
	return LCM;
}

결과>

아래는 유클리드 호제법(Euclidean Algorithm)을 이용해서 최대공약수 구하는 함수

//유클리드 호제법(Euclidean Algorithm)을 이용한 최대공약수 구하기
int getGCD_eu( int num1, int num2 )
{
	int temp;
	if(num1*num2==0){ //입력받은 두 수 중 하나라도 0이면
		fprintf(stderr, "GCD:: 수 입력을 다시해 주세요.\n");
		return 0;
	}
	if(num1>num2){ //입력받은 두 수 중 더 큰 수를 num2에 넣는다.
		temp=num1;
		num1=num2;
		num2=temp;
	}
	do{
		temp=num2%num1; //num2를 num1으로 나눈 나머지를 temp에 임시저장
		num2=num1;	//다시 제수는 피제수가,
		num1=temp; //나머지(temp)는 제수가 된다.
	}while(temp!=0); //num2가 num1로 나누어 떨어질 때 까지 반복
	return num2; //num2를 리턴
}