최대 공약수, 최소 공배수

https://mathbang.net/206#gsc.tab=0

최대공약수와 최소공배수의 관계

• 최대 공약수(Greatest Common Divisior, GCD): 두 수 이상의 여러 수의 공통된 약수
• 최소 공배수(Least Common Multiple, LCM): 둘 이상 수들의 공통된 배수 중 가장 작은 수

 두 수 A, B가 존재할 때 LCM(A,B) = A * B / GCD(A,B)의 관계가 성립한다.

1. GCD(A,B)는 A 및 B를 구성하고 있는 값이므로 A와 B 각각을 GCD(A,B) * n의 꼴로 나타낼 수 있다.
2. A 및 B에 각각 b, a를 곱하면 최소 공배수 LCM(A,B) = a * b * GCD(A,B)를 얻는다.
3. 등식 A = a * GCD(A,B)의 양변에서 GCD(A,B)를 나누면 a = A / GCD(A,B)를 도출할 수 있다.
4. LCM(A,B) = a * B = A / GCD(A,B) * B = A * B / GCD(A,B)를 얻을 수 있으며, B에 대해서도 동일하다.

 위 관계에 의해 최소 공배수는 두 수의 최대 공약수만 알고 있다면 쉽게 알아낼 수 있다. 이때, 최대 공약수는 유클리드 호제법에 의해 쉽게 얻어낼 수 있다. 유클리드 호제법은 다음 과정을 거쳐 최대 공약수를 도출할 수 있다. 

1. 두 수 A, B에 대해 r = A % B를 구한다.
2. B, r에 대해 r' = B % r을 구한다.
3. r'(2) = r % r'을 구한다 ...
4. 위 과정에 따라 r'(n) = 0이 나오면 r'(n-1) 이 최대공약수가 된다.

구체적인 증명은 위키피디아 링크를 참고하자. 위와 같은 과정을 알고리즘으로 나타내면 다음과 같다.

function getGCD(a,b) {
    while(b != 0) {
        let r = a % b;
        a = b;
        b = r;
    }
    return a;
}

 유클리드 호제법은 두 수가 서로소인지 판별할 때 사용되기도 한다. 서로소의 정의는 두 수 사이의 공약수가 1밖에 없음을 의미하는데, 이는 최대 공약수가 1이라는 의미와 동등하므로 GCD(a,b) = 1이라면 서로소라고 판정할 수 있다.

---

피자 나눠 먹기(2)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/120815

프로그래머스

위 문제에서 총 피자조각 수를 K라고 할때 K = LCM(N,6)이다. 이 값은 a * b * GCD(N, 6)으로 나타낼 수 있으며, b * GCD(N,6) = 6이라고 할 때 피자 판수 a = LCM(N,6) / 6 = N / GCD(N, 6)이다.

(1) 식을 이용하면 최소공배수를 계산하지 않고도 피자 판 수를 구할 수 있으므로, 이를 활용해서 코드를 작성했다.

function solution(n) {
  const val = gcd(n, 6);
  return Number(n / val);
}

function gcd(a, b) {
  while(b != 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

---

여러 수 사이의 최대 공약수, 최소 공배수

 여러 숫자에 대한 최대 공약수 및 최소 공배수는 숫자 2개에 대해 구하는 방식으로 연속적으로 구하면 된다. 예를 들어 10, 14, 20에 대한 최대 공약수 및 최소 공배수는 두 숫자 10, 14에 대해 계산된 최대 공약수 2, 최소 공배수 70을 남은 숫자 20과 다시 계산하여 각각 2, 140을 얻을 수 있다.

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=281&sca=99 

JUNGOL

# node가 입력 받기 좋은 구조는 아니라, 대신 파이썬 사용
def getGCD(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

count = int(input())
numbers = [*map(int, input().split(' '))]
gcd = numbers[0]
lcm = numbers[0]
for i in range(1,len(numbers)):
    gcd = getGCD(gcd, numbers[i])
    lcm = lcm * numbers[i] // getGCD(gcd, numbers[i])
print(gcd, lcm)