최대 공약수, 최소 공배수 구하는 문제

최대 공약수는 줄여서 GCD라고 쓴다. 두 수 A와 B의 최대 공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

최대공약수를 구하는 가장 쉬운방법은 2부터 A, B 중 작은 수까지 모든 정수로 나누어 보는 방법이다.

최대 공약수가 1인 두 수를 우리는 서로소라고 한다. 

 

int g = 1;
for(int i=2; i<=min(a,b); i++){
	if(a%2==0 &&b % i==0){
    	g=i;
    }
}

위의 코드보다 훨신 빠른 방법이 있다. 

바로 유클리드 호제법을 이용하는 방법이다. 

a를 b로 나누는 나머지를 r이라고 했을 때 

GCD(a,b)= GCD(b,r) 과 같다. 

r이 0이면 그 때 b가 최대 공약수이다. 

GCD(24,16) = GCD(16,8) = GCD(8,0) =8

 

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

-재귀 함수를 상용하지 않고 구현
int gcd(int a, int b){
	while( b != 0){
    	int r = a%b;
        a=b;
        b=r;
    }
   	return a;
 }

최소공배수

 

최소공배수는 줄여서 lcm이라고 한다. 

두수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.

최소 공배수는 GCD 를 응용해서 구할 수 있다. 

두 수 a,b의 최대공약수를  g라고 했을 때

최소공배수 l=g*(a/g) * (b/g) 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수