---

Reference

• 2501번 약수 구하기, Baekjoon online judge
• 11653번 소인수분해, Baekjoon online judge

---

1. 약수

약수(divisor, factor): 어떤 수를 나누어떨어지게 하는 수
-Reference. Divisor

1.1. 약수 판별 알고리즘

• 약수 판별 예: $6$의 약수는 $1, 2, 3, 6$
  $6 \div 1 = 6 \cdots 0$
  $6 \div 2 = 3 \cdots 0$
  $6 \div 3 = 2 \cdots 0$
  $6 \div 4 = 1 \cdots 2$
  $6 \div 5 = 1 \cdots 1$
  $6 \div 6 = 1 \cdots 0$

따라서, 자연수 $n$의 약수는 자연수 n을 자연수 1부터 n으로 차례대로 나누었을 때 나누어떨어지게 하는 자연수들이다.
따라서 약수들의 리스트를 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

def is_divisor(factor: int, n: int) -> boolean:
	if n % factor == 0:
    	return True
    else:
    	return False

def get_divisors(n: int) -> list:
	divisors = []
	for i in range(1, n + 1):
		if is_divisor(i, n):
    		divisors.append(i)
	return divisors

get_divisors(10)

>>> [1, 2, 5, 10]

---

1.2. 약수의 개수 알고리즘

• 약수의 개수 계산 예: $6$의 약수가 $(1, 2, 3, 6)$이므로 약수의 개수는 $4$
  $6 \div 1 = 6 \cdots 0$
  $6 \div 2 = 3 \cdots 0$
  $6 \div 3 = 2 \cdots 0$
  $6 \div 4 = 1 \cdots 2$
  $6 \div 5 = 1 \cdots 1$
  $6 \div 6 = 1 \cdots 0$

따라서, 자연수 $n$의 약수의 개수는 자연수 n을 자연수 1부터 n으로 차례대로 나누었을 때 나누어떨어지게 하는 자연수의 개수이다.
따라서, 위의 1.1. 약수 판별 알고리즘을 활용하여 약수의 개수를 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

def is_divisor(factor: int, n: int) -> boolean:
	if n % factor == 0:
    	return True
    else:
    	return False

def num_divisors(n: int) -> int:
	count = 0
	for i in range(1, n + 1):
		if is_divisor(i, n):
    		count += 1
	return count

num_divisors(10)

>>> 4

1.3. [백준 2501번] 약수 구하기

위의 1.1. 약수 판별 알고리즘과 1.2. 약수의 개수 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def is_divisor(factor: int, n: int) -> bool:
	if n % factor == 0:
    	return True
    else:
    	return False

def get_divisors(n: int) -> list:
	divisors = []
	for i in range(1, n + 1):
		if is_divisor(i, n):
    		divisors.append(i)
	return divisors

N, K = list(map(int, sys.stdin.readline().split()))
divisors = get_divisors(N)
if len(divisors) < K:
	print(0)
else:
	print(divisors[K + 1])

---

2. 소인수분해

소인수분해(prime factorization, integer factorization): 1보다 큰 자연수를 소인수(소수인 인수)들의 곱으로 나타냄. 합성수(1보다 큰 자연수 중에서 소수가 아닌 수)를 소수(1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수)의 곱으로 나타냄.
-Reference. Integer factorization

2.1. 소인수분해 알고리즘

• 소수: $2, 3, 5, 7, 11, 13 ...$
• 소인수분해 예: $72 = 2^3 \times 3^2, 135 = 3^3 \times 5$

따라서, 자연수 $n$의 소인수분해는 자연수 n을 1보다 큰 소수부터 n의 제곱근보다 작거나 같은 소수를 차례대로 나누었을 때 나누어떨어지게 하는 자연수이다.
따라서, 위의 1. 일반적인 방법을 활용하여 소인수분해하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

import math

def is_divisor(factor: int, n: int) -> bool:
	if n % factor == 0:
    	return True
    else:
    	return False

def is_prime_number(n: int) -> bool:
	if n == 2:
    	return True
	for i in range(2, n):
    	if is_divisor(i, n):
        	return False
    return True

def get_prime_numbers(limit: int) -> list:
	prime_numbers = []
	for i in range(2, limit + 1):
    	if is_prime_number(i):
        	prime_numbers.append(i)
    return prime_numbers

def get_prime_factors(n: int) -> dict:
	prime_factors = dict()
	for i in get_prime_numbers(int(math.sqrt(n))):
		while is_divisor(i, n):
    		prime_factors[i] = prime_factors.get(i, 0) + 1
            n //= i
	return prime_factors

get_prime_factors(17)

>>> {}

get_prime_factors(12)

>>> {2: 2, 3: 1}

2.2. 약수의 개수 알고리즘

• 약수의 개수 계산 예: $12 = 2^2 \times 3$ 이므로 약수의 개수는 $(2 + 1) \times (1 + 1) = 6$

$\times$	$1$	$2$	$2^2$
$1$	$1$	$2$	$4$
$3$	$3$	$6$	$12$

$12 \div (1 \times 1) = 12 \cdots 0$
$12 \div (1 \times 2) = 6 \cdots 0$
$12 \div (1 \times 2^2) = 3 \cdots 0$
$12 \div (1 \times 3) = 4 \cdots 2$
$12 \div (2 \times 3) = 2 \cdots 1$
$12 \div (2^2 \times 3) = 1 \cdots 0$

따라서, 자연수 $n$의 약수의 개수는 자연수 n을 소인수분해한 인수들의 곱으로 만들 수 있는 자연수의 개수이다.
따라서, 위의 2.1. 소인수분해 알고리즘을 활용하여 약수의 개수를 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

import math

def is_divisor(factor: int, n: int) -> bool:
	if n % factor == 0:
    	return True
    else:
    	return False

def is_prime_number(n: int) -> bool:
	if n == 2:
    	return True
	for i in range(2, n):
    	if is_divisor(i, n):
        	return False
    return True

def get_prime_numbers(limit: int) -> list:
	prime_numbers = []
	for i in range(2, limit + 1):
    	if is_prime_number(i):
        	prime_numbers.append(i)
    return prime_numbers

def num_prime_factors(n: int) -> int:
	prime_factors = dict()
	for i in get_prime_numbers(n):
		while is_divisor(i, n):
    		prime_factors[i] = prime_factors.get(i, 0) + 1
            n //= i
	return sum(prime_factors.values())

get_prime_factors(17)

>>> 0

get_prime_factors(12)

>>> 3

2.3. [백준 11653번] 소인수분해

위의 2.1. 소인수분해 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
import math

def is_divisor(factor: int, n: int) -> bool:
	if n % factor == 0:
    	return True
    else:
    	return False

def is_prime_number(n: int) -> bool:
	if n == 2:
    	return True
	for i in range(2, n):
    	if is_divisor(i, n):
        	return False
    return True

def get_prime_numbers(limit: int) -> list:
	prime_numbers = []
	for i in range(2, limit + 1):
    	if is_prime_number(i):
        	prime_numbers.append(i)
    return prime_numbers

def print_prime_factors(n: int) -> None:
	prime_factors = dict()
	for i in get_prime_numbers(n):
    	if n == 1:
        	break
		while is_divisor(i, n):
    		print(i)
            n //= i

print_prime_factors(int(sys.stdin.readline().split()[0]))

하지만, 소수를 먼저 계산하여 리스트로 담아두고 계산하는 방법은 너무 많은 반복문을 사용하여 시간 초과가 뜬다.

---

1.3.1. 분석

자연수들의 인수는 해당 자연수보다 작은 소수들의 곱으로 이루어져있다. 따라서, 작은 소수부터 주어진 자연수의 약수인지 검사한다면, 합성수는 자연스럽게 제거되므로 소수를 먼저 계산하여 리스트로 담아두고 계산하는 방법을 사용하지 않아도 된다.

이를 반영하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
import math

def is_divisor(factor: int, n: int) -> bool:
	if n % factor == 0:
    	return True
    else:
    	return False

def print_prime_factors(n: int) -> None:
	i: int = 2
    
	while n != 1:
    	while is_divisor(i, n):
        	print(i)
            n //= i
        i += 1

print_prime_factors(int(sys.stdin.readline().split()[0]))