[Python/파이썬] 백준 11653번 소인수분해

11653번: 소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

# 에라토스테네스의 체
def primeNum(n):
    num_arr = [False] * (n+1)
    res = []
    for i in range(2, n+1):
        if num_arr[i]:  # 이미 지워진 수라면
            continue
        if n % i == 0:
            res.append(i)
            for j in range(i * 2, n + 1, i):    # 자기자신은 제외하고 배수들 지움
                num_arr[j] = True
    return res

n = int(input())
if n != 1:
    for num in primeNum(n):
        while n % num == 0:
            print(num)
            n //= num

소수를 찾는 알고리즘인 에라토스테네스의 체를 이용하여 입력받은 N보다 작거나 같은 소수들을 찾아서 소인수분해를 한다.

처음에는 소수를 찾을 때 2부터 n+1까지 모두 확인하게 했는데 에라토스테네스의 체에 대해 다시 찾아보며 공부해보니 n+1까지 모두 확인할 필요는 없었다. int(n의 제곱근)까지만 확인해도 되는 것이었다. 그래서 다음과 같이 수정했다.

# 에라토스테네스의 체
def primeNum(n):
    num_arr = [True] * (n+1)
    for i in range(2, int(n ** 0.5) + 1):	# n의 제곱근까지만 확인
        if num_arr[i]:  # i가 소수라면
            for j in range(i * 2, n, i):    # 자기자신은 제외하고 배수들 지움
                num_arr[j] = False
    return [i for i in range(2, n + 1) if num_arr[i]]

n = int(input())
if n != 1:
    for num in primeNum(n):
        while n % num == 0:
            print(num)
            n //= num

 

• 에라토스테네스의 체

에라토스테네스의 체 (소수 판별 알고리즘)