약수(Divisor)

어떠한 수로 나누어 떨어지게(나머지가 0) 하는 수

$N$의 약수의 개수를 구하는 방법

1. 1부터 $N$ 이하의 정수로 $N$을 나누어서, 나머지가 0이 되는 수의 개수를 찾음

• 시간 복잡도: $O(N)$

2. 1부터 $\sqrt {N}$ 이하의 정수로 $N$을 나누어서, 나머지가 0이 되는 수의 개수를 찾고, 그 개수에 2를 곱함

• $N$이 제곱수면, 그 수에 1을 뺌

• 시간 복잡도: $O(\sqrt {N}$)

• 제곱수: 어떠한 정수의 제곱이 되는 정수

유클리드 호제법(Euclidean Algorithm)

• 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除) 원하는 수를 구하는 것을 의미

• 두 자연수 a, b에 대해서 (a > b) a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 동일

• 이 성질에 따라, b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수

예시

1071과 1029의 최대공약수

1. 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 계산 → 42

2. 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 계산 → 21

3. 42는 21로 나누어 떨어지므로, 1071과 1029의 최대공약수는 21

public static int GCD(int a, int b) {
	while (b != 0) {
    	int temp = b;
        b = a % b;
        a = temp;
	}
    return a;
}

def GCD(a, b):
	while b:
    	a, b = b, a % b
	return a

GCD와 LCM

1. GCD(Greatest Common Divisor = 최대공약수)

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

• LCM(a, b) = a $\times$ b ÷ GCD(a, b)

• 어떠한 두 수의 곱은, 그 두 수의 최대공약수와 최소공배수의 곱과 같다.

public static int LCM(int a, int b) {
	int gcd = GCD(a, b);
    return (a * b) / gcd;
}

표준 라이브러리 사용

• C++의 gcd, lcm 함수는 C++ 17 버전부터 지원 → numeric 모듈

#include <iostream>
#include <numeric>
using namespace std;

int main() {
	cout << gcd(18, 24) << '\n'; // 6
    cout << gcd(78696, 19332) << '\n'; // 36
    cout << gcd(33, 66) << '\n'; // 66
}

• Python에서는 math 모듈의 gcd(python 3.5 이상)와 lcm(python 3.9 이상) 함수 사용

import math
a = 12
b = 18

print("GCD: ", math.gcd(a, b))
print("LCM: ", math.lcm(a, b))

• Java는 지원하지 않음