[알고리즘 #6] 최대공약수 최소공배수 구하는 알고리즘 정리

** Responsive Ad **

1. 최대공약수 (Greatest Common Factor, GCF)

두 개 이상의 수가 공통으로 가지고 있는 약수 중 가장 큰 수

8의 약수 : 1, 2, 4, 8

12의 약수 : 1, 2, 3, 4, 6, 12

8과 12의 최대공약수 : 4

2. 최소공배수 (the Least Common Multiple, LCM)

두 개 이상의 수가 공통으로 가지는 배수 중 가장 작은 수 

3의 배수 : 3, 6, 9, 12, 15..

5의 배수  5, 10, 15, 20..

3과 5의 최소공배수 : 15

3. 서로소 (relative prime)

1 외의 공약수를 갖지 않는 두 수 

ex) 7, 11 는 1 외의 공약수가 없으므로 서로소이다.

4. 최대공약수 구하는 알고리즘

1) 유클리드(Euclidean) 공식 이용

  - 큰 수 A를 작은 수 B로 나누어 떨어지면, A, B의 최대공약수는 B

  - A를 B로 나누었을 때 나머지가 R이면, A, B의 최대공약수는 R과 B의 최대공약수와 같다.

    GCM(A,B) = GCM(B,R) / ex) GCM(15,12) = GCM(12,3)

  유클리드 공식 이용 알고리즘 순서

  a. 두 수 A, B 중 큰 수, 작은 수를 판별한다.

  b. 큰 수를 작은 수로 나누어 나머지를 구한다.

    - if 나머지가 0 : 작은 수가 최대공약수

    - if 나머지가 0이 아니면 : 나누기 반복

5. 최소공배수 구하는 알고리즘

최소공배수(LCM) = A x B / 최대공약수(GCD) 이므로 위의 최대공약수 알고리즘으로 최대공약수를 구하고 A x B x GCD 를 구하면 됨

A = a  x GCD / B = b x GCD (a, b는 서로소)

LCM = a x b x GCD = A x B / GCD

** 큰사각형 광고 **