최대공약수 , 최소공배수(유클리드 호제법)C언어

두 수의 최대 공약수를 구하는 방법 (유클리드 호제법)을 공부해 봤습니다.

 

두수 x, y 가 있을때, y가 0이 될때 까지 재귀함수로 구현해주면 됩니다.

예를들어 x가 25 y가 100이면 두수의 최대 공약수를 구하려면 사진과 같이 이루어지면 된다.

재귀 함수를 이룰 때는 y자리의 100은 x자리로 이동하고 x자리의 25는 y로 나누어 나머지가 y가 된다.

계속 재귀함수를 수행하면서 y가 0이 되었을때, x 자리의 있는 수가 최대공약수 이다.

유클리드 호제법

이를 코드로 구현해보자

#include<stdio.h>
int gcd(int x, int y){
    if (!y) //y==0
		return x;
	return gcd(y, x % y);
}
int main(){
    int a, b;
	scanf("%d %d",&a,&b);
	printf("%d\n",gcd(a,b));  //최대공약수
	printf("%d\n", a * b / gcd(a,b)); //최소공배수
    
    return 0;
}

최대공약수를 알아 냈으면 최소공배수를 구하는 것은 더 쉽다.

두수의 곱은 최대공약수와 최소공배수를 곱한 값과 같으므로 

x=25 , y=100 

x * y =2500 

2500=최대공약수(25) * 최소공배수

최소공배수 = 2500 / 25

따라서 최소공배수는 100이다

#include<stdio.h>
int gcd(int x, int y){
	if (!y) //y==0
		return x; //최대공약수
	return gcd(y, x % y);
}
int main(){
    int a, b;
	scanf("%d %d",&a,&b);
	printf("%d\n",gcd(a,b));  //최대공약수
	
    return 0;
}

풀어볼만한 문제