[알고리즘] 최대 공약수와 최소 공배수

최대공약수와 최소공배수를 구해보자 

학생때 배운 수학을 떠올려보면 최소 공배수는 두 수 a,b를 곱한 값을 최대공약수로 나눈 값이다.

그러나 최대공약수를 구하는 방법이 떠오르지 않았고 한 번 직접 코드를 짜봤다.

int a = 30;
int b= 20;
int gcd = 0;

for (int i=1; i<b;i++){
  if(a%i==0 && b%i==0){
    gcd =i;
  }
}

int lcm = a*b/gcd;

그러나 이 방법은 시간이 오래걸리고 a>=b인 경우에만 사용이 가능하다.

 

이제 검색을 해봤고 "유클리드 호제법"으로 구하는 법을 알게 되었다.

1. 두 수 a,b가 있을 때 r은 a를 b로 나눈 나머지이다. 

2. a,b의 최대공약수는 b,r의 최대공약수와 같다.

3. 이 과정을 b가 0이 될 때까지 반복한다.

 

(ex)

a=30, b=20 인 경우에

gcd(30, 20) -> r = 10

그 다음은 a자리에 b인 20을 넣고 b자리에 r값 10을넣는다.  gcd(20, 10) -> r = 0;  r이 0이므로 종료; 최대공약수는 10

(ex2)

a=20, b=15 인 경우에 gcd(20, 15) -> r = 5

그 다음은 a자리에 b인 15을 넣고 b자리에 r값 5을넣는다.   gcd(15, 5) -> r = 0;  r이 0이므로 종료 ; 최대공약수는 5

(ex3)

a=21, b=12 인 경우에 gcd(21,12) -> r = 9

그 다음은 a자리에 b인 12을 넣고 b자리에 r값 9을넣는다.  gcd(12, 9) -> r = 3

그 다음은 a자리에 b인 9을 넣고 b자리에 r값 3을넣는다.  gcd(9, 3) -> r = 0;  r이 0이므로 종료 ; 최대공약수는 3

int a;
int b;
int r;
int lcm = a*b ;

while(b!=0){
	r = a%b;
    a = b;
    b = r;
}
int gcd = a;
lcm /= gcd;

다만 이 경우에도 a>=b 여야했다.

 

 

 

 

 

 

 

 

[ 알고리즘을 공부한 내용을 정리해보는 공간입니다. 부족한 부분이나 잘못된 부분 지적해주시면 감사하겠습니다.]