소수와 소인수 분해 (Prime Number, Prime Factorization)

소수 (Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 의미한다.
예를 들어, 5는 1x5 혹은 5x1로, 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 소수에 해당한다.
반대개념으로 합성수(Composite Number)가 있는데 여기서는 소수에 집중해보자.

정수론의 기본 정리에 의해, 모든 자연수는 꼭 한가지 방법으로 "소수의 곱"으로 표현할 수 있고 이를 소인수 분해의 일의성이라고 한다. 즉, 곱셉의 관점에서 소수는 자연수를 이루는 성분이라 할 수 있다. 아래 예시를 보자.

$$23244 = 2^2 \times 3 \times 13 \times 149$$

`23244`는 약수의 순서를 무시하면 단 1개의 방법으로 소인수 분해가 된다.
현재까지 알려진 가장 간단한 소수를 찾는 방법이 1가지가 있는데, 바로 에라토스테네스의 체 알고리즘을 이용한 방법이다. 이를 포함해서 소수와 소인수분해에 대한 알고리즘을 하나씩 살펴보자.

1. 소인수 분해

1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것을 말한다. 정의에서부터 1을 포함하지 않기에 2부터 시작해야하며 2로 나누지 못할 경우 2에서 +1을 해주면서 나눗셈이 가능한지 체크하면 된다.

def PrimeFactorization(target_number):
    currentDecimal = 2

    while currentDecimal <= target_number:
        if target_number % currentDecimal == 0:
            print(currentDecimal)
            target_number = target_number / currentDecimal
        else:
            currentDecimal = currentDecimal + 1
            
# PrimeFactorization(9) : 3 x 3
# 3
# 3

2. 소수 : 전체 순회

전체 순회방식은 가장 심플하다. 정의에 입각한 구현방식인데, 소수의 정의는 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수이다. 즉, 1을 제외하면 어떤수로도 나누어지면 안된다는 것이다. 이 부분에 중심을 두고 구현한 것으로, 아래 코드는 `x`가 소수인지 아닌지 판별하는 코드이다.

# 전체 순회방식
def primenumber(x):
    for i in range(2, x):	# 2부터 x-1까지의 모든 숫자
        if x % i == 0:		# 나눠떨어지는게 하나라도 있으면 False
            return False
    return True

3. 소수 : 제곱근 범위 순회

위 전체순회랑 별 다를게 없다. 단지 범위만 `x`의 제곱근으로 바뀌었을 뿐!

# 제곱근 범위 순회방식
import math

def primenumber_2(x):
    for i in range(2, int(math.sqrt(x) + 1)):	# 2부터 x의 제곱근까지의 숫자
        if x % i == 0:		# 나눠떨어지는 숫자가 있으면 소수가 아님
            return False
    return True

4. 에라토스테네스의 체

다음과 같은 순서로 알고리즘을 구현하면 에라토스테네스의 체를 구현할 수 있다.
1. 찾고자 하는 범위의 자연수를 나열한다.
2. 1은 지운다.
3. 2부터 시작하여, 2의 배수를 지워나간다.
4. 다음 소수의 배수를 모두 지운다.

# 에라토스테네스의 체
import math

def primenumber_3(x):
    n = 1000	# 2부터 1000까지 모든 수에 대하여 소수를 찾을 것이다.
    array = [True for i in range(n + 1)] # 0,1을 제외한 모든 숫자가 소수(True)인 것으로 설정하고 시작한다.

    # 에라토스테네스의 체 알고리즘
    for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인
        if array[i] == True:	# i가 소수인 경우 i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1
                
    #모든 소수 출력
    for i in range(2, n + 1):
        if array[i]:
            print(i, end = ' ')