소인수분해

들어가며

안녕하세요. 소인수분해에 대한 개념과, 해당 개념을 코드로 작성해보도록 하겠습니다.
먼저, 소인수분해에 알아보도록 하겠습니다.

먼저, 85라는 숫자를 소인수분해해보면 다음과 같은 결과가 나옵니다.

45 = 3 x 3 x 5 = 3^2 x 5

보이는 것처럼, 45처럼 특정한 숫자 또는 식을, 다른 숫자들 또는 식의 곱셈으로 표현하는 방식을 인수분해라고 하며, 그 중에서도, 어떤 특정한 숫자를 소수인 인수의 곱셈으로 표현하여 숫자를 분해하는 방법을 소인수분해라고 합니다.

---

소수

그러면 소수가 뭔지 한번 짚고 넘어가겠습니다.
소수는 1과 자기 자신만으로 약분되는 수입니다.
1부터 10까지의 수 중에, 다음과 같은 수는 소수입니다.

Prime number : 2,3,5,7

반대로, 1부터 10까지 수 중 소수가 아닌 수는 다음과 같습니다.

Not Prime number : 4,6,8,9,10

2,3,5,7 같은 경우에는 1과 자기 자신만으로 약분이 됩니다. 그 외에는 다른 약수가 존재하지 않습니다.
4,6,8,9,10 같은 경우에는 1과 자기 자신외에 다른 약수들이 존재합니다.

4의 경우 : 1,2,4  
6의 경우 : 1,2,3,6  
8의 경우 : 1,2,4,8  
9의 경우 : 1,3,9  
10의 경우 : 1,2,5,10  

점점 숫자를 키워나가다보면, 많은 소수들이 홀수지만, 소수라고 해서 꼭 홀수인 것은 아닙니다. 대표적으로 2는 짝수입니다.
그리고, 1은 소수가 아닙니다. 소수라는 것을 우리가 1과 자기 자신만으로 약분되는 수, 즉 약수가 2개라고 정의했는데, 1은 약분되는 수가 1 = 자기자신이므로 한 개 밖에 없어서, 소수라고 정의할 수 없습니다.

이제 다시 소인수분해로 돌아가보도록하겠습니다.

---

소인수분해

소인수분해란 앞서 언급했듯이, 어떤 수를 소수의 곱셉으로 표현하는 것을 말합니다. 즉, 어떤 수를 소수로 쪼개는 것이라고 볼 수 있습니다. 75라는 숫자를 예로 들어보도록 하겠습니다.

75 

이 숫자를 쪼갤 수 있는 가장 작은 소수부터 찾아보도록 하겠습니다.
앞서 언급한 소수들은 2,3,5,7 같은 것들이 있었습니다.
75를 나눠서 나머지가 0인, 즉 나눈 결과인 몫이 정수인 숫자를 찾아봅시다.
만약 나눴을 때 결과가 정수가 아니라면 해당 소수는 75를 나눌 수 있는 소수가 아닌거죠.

75/2 = 37.5  #나눈 결과가 정수가 아니므로 2는 75의 인수가 아님
75/3 = 25    #나눈 결과가 정수이므로 3은 75의 인수임

나눠보니, 75라는 숫자는 3을 인수로 가지는 숫자인 것을 알 수 있었습니다.
3은 75의 인수이자 소수이므로, 줄여서 소인수라고 부를 수 있겠죠.
그럼 3으로 나누었으니, 몫인 25에 대해서도 계속해서 소인수를 찾아보도록 하겠습니다.

25/2 = 12.5     # 나눈 결과가 정수가 아니므로 2는 25의 인수가 아님
25/3 = 8.3333.. # 나눈 결과가 정수가 아니므로 2는 25의 인수가 아님
25/4            # 4는 소수가 아니므로 패스
25/5 = 5

25를 5로 나누면 몫이 5가 남지만, 남은 숫자인 5는 소수이므로 더이상 나눌 수가 없으므로 소인수분해는 여기서 종료됩니다. 때문에 75를 소인수분해하면 이 글의 처음에서 언급했던 것처럼 다음과 같이 정리해볼 수 있습니다.

75 = 3 x 25 = 3 x 5 x 5

그리고, 이렇게 지수가 반복되는 경우에는 지수 표기법을 이용해서 정리할 수 있으므로,
지수 표기법을 이용해서 작성하면, 다음과 같이 작성해볼 수 있겠습니다.

75 = 3 x 5^2

---

코드로 만들어보기

앞서 진행했던 소인수분해를 프로그래밍으로 구현해보도록 하겠습니다. 먼저 과정을 정리해봅시다.

1. 소인수분해를 하고자 하는 숫자를 준비한다
2. 1의 숫자가 1인 경우 작동하지 않는다.
3. 1의 숫자를 가장 작은 소수인 2부터 나눈다.
   3-1. 나누어 떨어질 경우 해당 소수는 소인수이므로 해당 숫자를 기록하고, 몫인 숫자로 1번을 진행한다. 
   3-2. 나누어 떨어지지 않을 경우, 넘어간다
4. 종료되었을 때, 해당 3-1에서 기록한 소인수를 확인한다.

위 과정을 코드로 작성해봅시다.
소수를 판별하는 부분은 is_prime이라는 별도의 함수로 작성했습니다.

def is_prime(num): #소수를 체크합니다.
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def prime_factorization(n): #소인수 분해를 할 숫자를 n이라고 표현합니다.
    factors = [] #해당 리스트에 소수가 기록됩니다.
    divisor = 2  #소수를 담당하는 변수입니다.

    if n == 1:
        return [1]  # 1의 경우 소인수분해 결과는 자기 자신인 1을 반환합니다.

    while n > 1:  # n이 1인 경우 작동하지 않습니다.
        while n % divisor == 0: # n을 1이 아닌 가장 작은 수인, 2부터 나눕니다. 나누어 떨어질때만 작동합니다(인수) 
            if is_prime(divisor): #나누는 수(divisor)가 소수일때만
                factors.append(divisor) # 나누는 숫자를 기록합니다.
                n //= divisor # n을 divisor로 나눈 몫을 n에 다시 대입합니다. 
            else: #소수가 아니면 넘어갑니다.
                break
        divisor += 1 #divisor를 올리고, 인수인지 여부를 다시 판단합니다.

    return factors #기록한 숫자들을 반환합니다.

number = int(input("소인수 분해를 할 숫자 : "))
print(number, "의 소인수분해 결과:", prime_factorization(number))

주석을 제거해보면 다음과 같습니다.

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def prime_factorization(n): 
    factors = [] 
    divisor = 2  

    if n == 1:
        return [1] 

    while n > 1:  
        while n % divisor == 0: 
            if is_prime(divisor): 
                factors.append(divisor) 
                n //= divisor 
            else:
                break
        divisor += 1 

    return factors

number = int(input("소인수 분해를 할 숫자 : "))
print(number, "의 소인수분해 결과:", prime_factorization(number))

앞서 언급한 과정과 코드를 비교해보면, 과정을 거의 그대로 적은 것을 볼 수 있습니다.
각 과정에서 어떤 식으로 진행하는지, 그리고 어떤 과정을 반복하는지를 잘 구분해보면 좋을 것 같습니다.

정리하며

소인수분해는 대학 과정 이상으로 올라가면, 암호화와 관련하여 다시 공부하게 되는 분야입니다.
다양한 소인수분해 방법이 있으므로 한번 찾아보면 또다른 재미를 찾을 수 있을 것 같습니다.

중학생이신 분들은 여러분들이 배운 소인수분해가 어떤 과정을 거치는지,
해당 과정이 어떻게 코드로 변환되는지 유심히 보면 생각보다 어렵지 않다는 것을 알게 될겁니다.

궁금하신 내용이 있다면 댓글로 달아주세요. 감사합니다.