알고리즘 - 소인수 분해

소인수 분해

• 소인수 : 어떤 자연수의 인수(약수) 중에서 소수인 것
• 소인수 분해 : 1보다 큰 자연수를 소인수만의 곱으로 나타낸 것
  ex) 45 = 3 x 3 x 5

소인수 분해 코드

def factorize(n):
    factor = 2      # 시작 값
    factors = []    # 소인수를 담을 리스트
    
    while (factor**2 <= n):           # n까지 확인하지않고 n의 제곱근까지 확인
        while (n % factor == 0):      # factor의 값이 n의 소인수이면 루프
            n = n // factor            # n의 값을 변경해준다.
            factors.append(factor)     # 소인수이기 때문에 리스트에 담는다.
        factor += 1         # 소인수가 아니면 루프를 빠져나와 factor의 값을 1더한다.
    
    if n > 1:
        factors.append(n)   # 루프를 다 돌고 n의 값이 더이상 나눠지지 않는데 n이 1보다 크면 그 값도 소인수이기 때문에 추가
    
    return factors

---

소인수 찾기

def findFactors(n):
    factor_list = factorize(n)   # 사전 제작한 factorize 함수 사용
    factors = []   # 소인수를 담을 리스트
    
    for i in factor_list:
        if (i not in factors):    # factors 리스트에 소인수 값이 없으면 추가
            factors.append(i)
            
    return factors

findFactors(3757208)

사전 제작한 함수를 불러오는 방법 말고 세트로 중복을 없애고 리스트로 바꿔서 값을 반환하는 방법도 있다.

def factorize(n):
    factor = 2      # 시작 값
    factors = []    # 소인수를 담을 리스트
    
    while (factor**2 <= n):           # n까지 확인하지않고 n의 제곱근까지 확인
        while (n % factor == 0):      # factor의 값이 n의 소인수이면 루프
            n = n // factor            # n의 값을 변경해준다.
            factors.append(factor)     # 소인수이기 때문에 리스트에 담는다.
        factor += 1         # 소인수가 아니면 루프를 빠져나와 factor의 값을 1더한다.
    
    if n > 1:
        factors.append(n)   # 루프를 다 돌고 n의 값이 더이상 나눠지지 않는데 n이 1보다 크면 그 값도 소인수이기 때문에 추가
    
    return list(set(factors)

** 출처

• 주니온TV 아무거나연구소 - 코린아, 코딩하자 (with 파이썬)