프로그래머가 보는 수학 - 소인수분해

사전지식 : https://aaaag.tistory.com/19

프로그래머가 보는 수학 - 거듭제곱

사전지식 : https://aaaag.tistory.com/22

프로그래머가 보는 수학 - 인수와 소인수

---

소인수분해 : 자연수를 소인수들의 곱으로 표현한 것

---

• 12 == 2² * 3
• 자연수를 소수가 나올 때까지 계속 나눈다

30을 소인수분해 할 경우

• 30을 소인수분해 할 경우
  • 30 % 5= 6
  • 6 % 2 = 3
• 2 * 3 * 5 == 30

---

프로그래밍 구현

# -*- coding: utf-8 -*-
import sys

number = int(input())

resultTuple = ()
value = 2
maxValue = number
while(True):
    result = maxValue % value
    #result가 0일경우 소수
    if result == 0:
        resultTuple = resultTuple + (value,)
        maxValue = int(maxValue / value)
        continue
    #나누는수가 나누어야될 값보다 커졌다면 break
    elif value >= maxValue:
        break
    #0이 아닐경우 다음 나누는수 증가
    else:
        value = value + 1
        continue

if len(resultTuple) == 1:
    sys.exit(0)

print(f"prime factorization : {resultTuple}")

---

소인수분해로 약수 구하기

• 공식 : 주어진 수를 소인수분해 한 다음 각각 거듭제곱의 약수를 모두 구한 다음 서로 곱한다.

---

• 108의 약수를 구할경우 소인수분해 하면 2² * 3³
• 2²의 약수는 1, 2, 4 == 1, 2, 2²
• 3³의 약수는 1, 3, 9, 27 == 1, 3, 3², 3³

x	1	3 == 3¹	9 == 3²	27 == 3³
1	1	3	9	27
2 == 2¹	2	6	18	54
4 == 2²	4	12	36	108

• 약수는 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108 이다
• 테이블의 가로 세로의 값은 1을 포함한 지수의 값을 1씩 증가시킨 약수들이다

 

• 2250의 약수를 구할경우 소인수분해 하면 2 * 3² * 5³
• 2의 약수는 1, 2 == 1, 2
• 3의 약수는 1, 3, 9 == 1, 3, 3²
• 5의 약수는 1, 5, 25, 125 == 1, 5, 5², 5³
• 2와 3의 약수를 곱한다

x	1	3 == 3¹	9 == 3²
1	1	3	9
2 == 2¹	2	6	18

• 2와 3의 곱으로 나온 약수와 5의 약수를 곱한다

x	1	5 == 5¹	25 == 5²	125 == 5³
1	1	5	25	125
2	2	10	50	250
3	3	15	75	375
6	6	30	150	750
9	9	45	225	1,125
18	18	90	450	2,250

• 약수는 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 125, 150, 225, 250, 375, 450, 750, 1125, 2250 이다

---

프로그래밍 구현

# -*- coding: utf-8 -*-
import sys

def PrimeFactorization():
    number = int(input())
    
    resultDic = {}
    value = 2
    maxValue = number
    while(True):
        result = maxValue % value

        #result가 0일경우 소수
        if result == 0:
            if value in resultDic:
                #resultDic[value] = resultDic[value] + 1
                addValue = resultDic[value][-1] * value
                resultDic[value] = resultDic[value] + [addValue]
            else:
                #resultDic[value] = 1
                resultDic[value] = [1, value]

            maxValue = int(maxValue / value)
            continue
        #나누는수가 나누어야될 값보다 커졌다면 break
        elif value >= maxValue:
            break
        #0이 아닐경우 다음 나누는수 증가
        else:
            value = value + 1
            continue

    return resultDic

resultDic = PrimeFactorization()
resultPopItem = resultDic.popitem()[1]

if len(resultDic) == 0:
    print(f"{resultPopItem}")
    sys.exit(0)

resultList = []
for valuesList in resultDic.values():
    if len(resultList) != 0:
        resultPopItem = resultList.copy()
        resultList.clear()

    for lValue in valuesList:
        for rValue in resultPopItem:
            result = lValue * rValue
            resultList.append(result)

resultList.sort()
print(f"{resultList}")

---

소인수분해로 약수 개수 구하기

• 공식 : 각 소인수의 지수들마다 +1 한 다음 서로 곱한다.

---

• 18의 약수는 2 * 3²
• 2 * 3²을 공식대로 하면 (1 + 1) * (2 + 1) = 약수의 개수
• 약수의 개수는 6개

---

프로그래밍 구현

# -*- coding: utf-8 -*-
import sys

def PrimeFactorization():
    number = int(input())
    
    resultDic = {}
    value = 2
    maxValue = number
    while(True):
        result = maxValue % value

        #result가 0일경우 소수
        if result == 0:
            if value in resultDic:
                resultDic[value] = resultDic[value] + 1
            else:
                resultDic[value] = 1

            maxValue = int(maxValue / value)
            continue
        #나누는수가 나누어야될 값보다 커졌다면 break
        elif value >= maxValue:
            break
        #0이 아닐경우 다음 나누는수 증가
        else:
            value = value + 1
            continue

    return resultDic

resultDic = PrimeFactorization()
#최소한의 약수 개수 == 소수
resultPopItem = resultDic.popitem()[1] + 1

if len(resultDic) == 0:
    print(f"{resultPopItem}")
    sys.exit(0)

resultList = 0
for value in resultDic.values():
    if resultList != 0:
        resultPopItem = resultList
        resultList = 0

    resultList = (value + 1) * resultPopItem

print(f"{resultList}")