약수의 개수와 최대공약수, 최소공배수 (Count of Divisor & GCD, LCM)

수론에서 약수(=divisor) 혹은 인수(=factor)는 어떤 수를 나누어떨어지게 하는 수를 말한다.
두 정수 `a,\;b`에 대하여 `b=ac`를 만족하는 정수 `c`가 존재한다면 `a`를 `b`의 약수라고 말하고 `a|b`로 표기한다.
모든 정수는 1과 -1을 약수로 가진다. 또한 모든 정수는 자기자신과 그 반수(더했을 때 0이 되는 수)를 약수로 가진다. 예시를 들면 이렇다. 12의 모든 양의 약수는 1,2,3,4,6,12이다. 약수는 음수일 수 있으며, 12의 모든 음의 약수는 -1, -2, -3, -4, -6, -12이다.

이제는 성질을 알아보자. 약수를 논할때 빠질 수 없는것이 바로 배수와의 관계이고, 가장 빈번하게 등장하는 개념이 최대공약수와 최소공배수일 것이다. 요거까지 정리해보자.
우리는 위에서 말한 약수의 정의를 까지고 짝수/홀수를 재정의해볼 수 있다. 여태껏 2로 나눈 나머지가 0인수를 짝수, 그렇지 않은수를 홀수라고 했다면 이제는 다음과 같은 표현을 사용할 수 있다.

• 짝수(even) : 2를 약수로 가지는 정수
• 홀수(odd) : 2를 약수로 가지지 않는 정수

여기서 특이한 점! 홀수는 홀수만을 약수로 가지고, 짝수는 홀수, 짝수 관계없이 약수를 가지며 2의 거듭제곱은 짝수를 약수로 가진다.
두 정수의 약수가운데 가장 큰 하나를 최대공약수라고 한다. 즉, 두 정수 `a, b`의 최대 공약수를 `gcd{a, b}`로 표기하고 통상적으로 `gcd`라고 부른다. 이 `gcd`가 1인 두 정수를 '서로소'라고 한다.

약수의 개수는 앞선 포스팅의 소인수분해를 하는과정에서 쉽게 구할 수 있다.
소인수분해를 한 형태에서 각 소인수가 곱해진 지수에 +1을 한후 그것들을 다 곱한 것이다.
예를 들자면, `72`의 소인수 분해는 `2 \times 2 \times 2 \times 3 \times 3`이다. 즉, `2^3 \times 3^2`이므로 각 소인수의 지수에 +1을 한 값들을 곱한 결과인 `(3+1) \times (2+1) = 4 \times 3 = 12`가 되는것이다. 즉, 72의 약수의 개수는 12이다. 

위의 과정을 따라 임의의 수 `N`의 약수의 개수를 구하는 코드를 구현해본다고 하자. 장황하게 썼지만 결국은 아래의 과정을 거쳐야 한다. 

• 임의의 수 `N`에 대해 소인수 분해를 한다. (혹은 직접 약수를 구한다)

그렇다보니 결국은 앞 포스팅과 구조가 비슷해질 수밖에 없는 것이다.

# 약수의 개수를 구하는 함수
def countDivisor(n):

    divisors = []

    for i in range(1, n + 1):
        if (n % i == 0) :
            divisors.append(i)

    return len(divisorsList)

여기서 조금 더 개선을 한다고 한다면, 반복하는 범위를 줄일수있겠다. 
약수의 정의에 따르면 `N = a \times b`로 표현될 것이다. 항상 약수를 구하면 그 짝이되는 숫자가 존재한다는 말이다.
즉, 반복문의 범위를 N의 제곱근까지로 제한을 둬도 아무 문제가 없다! (다만, 같은 숫자가 2번 들어오는것에 주의하자. )

# 반복범위를 줄인 약수의 개수 구하기
def countDivisor(n):

    divisors = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisors.append(i) 
            if ((i**2) != n) : 
                divisors.append(n // i)
    
    return len(divisors)

그럼 앞에서 짧게 언급했던 최대공약수와 최소공배수를 살펴보자.
공약수란, 두 수 혹은 그 이상의 수에 공통인 약수를 말한다. 공배수도 다를바 없다. 공통인 배수를 뜻하는 말이다.
최대공약수와 최소공배수는 각각 공통인 약수중 최댓값, 공통인 배수중 최솟값을 의미한다.
다음 예시를 보자.
12의 약수 : 1, 2, 3, 4, 6, 12
18의 약수 : 1, 2, 3, 6, 9, 18
이들 중 공약수는 1, 2, 3, 6이 해당하고 최댓값인 6이 `gcd`에 해당한다. 다만, 이 방법은 주어지는 숫자에 따라 너무 오래걸릴 수 있다.
그래서, 유클리드 호제법이라는 것을 이용한 코드를 살펴보겠다!

def gcd(a, b):
    if a < b:
        a, b = b, a
    
    while b != 0:
        a, b = b, a % b
    
    return a

`gcd`가 구해졌다면 `lcm`을 구하는것은 간단하다.

$$gcd(a,b)=\frac{|ab|}{lcm(a,b)}$$

바로 이 수식을 이용한 것인데 아래 코드를 보면 된다.

def lcm(a, b):
    return a * b // gcd(a, b)