기본적인 소인수분해법

II-eugene-II Note

기본적인 소인수분해법

$N = 360 = 2^{3} \times 3^{2} \times 5$ 일 때, 소인수분해의 결과인 [2, 2, 2, 3, 3, 5]를 얻고 싶을 때는 어떻게 해야할까요?
기본적인 소수 판별법 처럼, 기본 아이디어는 $2$ 부터 $\sqrt{N}$ 까지 일일이 나누어보는 것 입니다.
소수판별법에서는 그저 딱 한 번만 나눠보고 말면 될 일이었지만, 소인수분해에서는 몇번 나누어떨어지는지도 굉장히 중요합니다.
예를 들어, 위의 예시처럼 360을 그냥 평범한 소수 판별법처럼 한번만 나눠보고 만다면 결과는 [2, 3, 5]만 나오게 될 것입니다.
따라서, N을 진짜로 변형시켜야 합니다. N이 2로 나누어떨어지는걸 확인했으면 $N := \frac{N}{2}$ 로 두고, 또 2로 나누어떨어지면 또 $N := \frac{N}{2}$ 를 하고...를 반복해야합니다.
그러므로 이런 소인수분해법에서는 while 문을 같이 사용하는것이 적절합니다.
언제까지 나누어주면 좋을까요? 계속 나누고 나누고 나누다가 N이 1이 되면 종료하면 됩니다.

방법 1. d = 2부터 계속 일일이 나눠주고, d를 하나씩 늘려나가다가 N이 1이면 종료하기

	def factorize(N):
	factorList = []
	d = 2
	while N != 1:
	while N % d == 0:
	factorList.append(d)
	N //= d
	d += 1
	return factorList

view raw factorize0.py hosted with ❤ by GitHub

꼭 N = 1이 되어야만 종료해야할까요?
위 방법대로라면,

$N = 20014 = 2 \times 10007$ (10007은 소수)에 대해서, d가 10007이 될 때까지 계속 나누어보게 됩니다.
소수 판별법에서 이야기 했던 것 처럼, p * p > N인 소수 p에 대해서는 N이 나누어떨어질 수가 없습니다.
따라서, d * d > N이 되면 종료하게끔 하면 더 빠르게 종료할 수 있습니다. 이렇게 되면 위의

$N = 20014 = 2 \times 10007$ 는

$101 \times 101 > 10007$ 에서 d = 101이 되는 순간 종료하게 됩니다.
단, 이때는 N이 1이 아니라면 factorList에 N을 넣어주어야 합니다. 최후에 남은 1이 아닌 N은 원래 N의 소인수 입니다.

방법 2. d = 2부터 계속 일일이 나눠주고, d를 하나씩 늘려나가다가 d * d > N이면 종료하기

	def factorize(N):
	factorList = []
	d = 2
	while d * d <= N:
	while N % d == 0:
	factorList.append(d)
	N //= d
	d += 1
	if N != 1: factorList.append(N)
	return factorList

view raw factorize1.py hosted with ❤ by GitHub

꼭 d = 2부터 시작해야 하는 것은 아닙니다.
d = 2로 계속 나누어 떨어질때까지 계속 나누고나면, d = 4, d = 6, d = 8...로는 나누어떨어질 리가 없습니다.
따라서, 2는 따로 처리하고 d = 3부터 시작하여 2씩 늘려갈 수 있습니다.

방법 3. d = 2는 따로 처리하고, d = 3부터 계속 일일이 나눠주고, d를 둘씩 늘리기

	def factorize(N):
	factorList = []
	d = 3
	while N % 2 == 0:
	factorList.append(2)
	N //= 2
	while d * d <= N:
	while N % d == 0:
	factorList.append(d)
	N //= d
	d += 2
	if N != 1: factorList.append(N)
	return factorList

view raw factorize2.py hosted with ❤ by GitHub

그냥 간단하게 하면 이정도로 소인수분해는 끝이지만, 보통 여기서 더 나아가서 Lehman 소인수분해, 폴라드-로 소인수분해 등 다양한 시간복잡도 줄이기 방법이 동원됩니다.