[PYTHON/COMMON] 소인수 분해(Factorization) 리스트 구하기

icodebroker COMMON 2024-06-18

■ 소인수 분해(Factorization) 리스트를 구하는 방법을 보여준다.

▶ 예제 코드 (PY)


import math

def getPrimeNumberList(value):
    isPrimeNumberList = [True] * value
    maximumLength     = math.ceil(math.sqrt(value))
    for i in range(2, maximumLength):
        if isPrimeNumberList[i]:
            for j in range(i + i, value, i):
                isPrimeNumberList[j] = False
    return [i for i in range(2, value) if isPrimeNumberList[i]]

def getFactorizationList(value):
    factorizationList = []
    for primeNumber in getPrimeNumberList(value):
        count = 0
        while value % primeNumber == 0:
            value /= primeNumber
            count += 1
        if count > 0:
            factorizationList.append((primeNumber, count))

    return factorizationList

factorizationList = getFactorizationList(12)

print(factorizationList)

"""
[(2, 2), (3, 1)]
"""

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

import math

def getPrimeNumberList(value):

isPrimeNumberList = [True] * value

maximumLength = math.ceil(math.sqrt(value))

for i in range(2, maximumLength):

if isPrimeNumberList[i]:

for j in range(i + i, value, i):

isPrimeNumberList[j] = False

return [i for i in range(2, value) if isPrimeNumberList[i]]

def getFactorizationList(value):

factorizationList = []

for primeNumber in getPrimeNumberList(value):

count = 0

while value % primeNumber == 0:

value /= primeNumber

count += 1

if count > 0:

factorizationList.append((primeNumber, count))

return factorizationList

factorizationList = getFactorizationList(12)

print(factorizationList)

"""

[(2, 2), (3, 1)]

"""