2024.7.8 백준(Python) 11653 소인수분해

소인수분해 

문제

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

입력

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

출력

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

예제 입력 1 

72

예제 출력 1 

2
2
2
3
3

예제 입력 2 

3

예제 출력 2 

3

예제 입력 3 

6

예제 출력 3 

2
3

예제 입력 4 

2

예제 출력 4 

2

예제 입력 5 

9991

예제 출력 5 

97
103

 

정답 코드

def get_prime(num):
    add = 0
    # 2부터 num까지의 모든 수로 num을 나누어봄
    for i in range(2, num + 1):
        if num % i == 0:
            add += i

    # 나누어 떨어지는 모든 수의 합이 num과 같다면 소수
    if add == num:
        return True
    else:
        return False

# 소인수 분해할 수를 입력받음
factorization = int(input())

# 입력된 수가 1이면, 소인수 분해가 불가능하므로 종료
if factorization == 1:
    exit()

# 소인수를 저장할 리스트 초기화
prime_Factorlist = []

# 소인수를 찾기 시작할 초기 값 설정
num = 2

# 무한 반복을 통해 소인수를 찾음
while 1:
    # 현재 num이 factorization의 소인수인지 확인
    # num이 factorization을 나누어 떨어지고, num이 소수일 경우
    if factorization % num == 0 and get_prime(num):
        # factorization을 num으로 나누어 나머지 값을 얻음
        factorization = factorization // num
        # num을 소인수 리스트에 추가
        prime_Factorlist.append(num)
    # factorization이 1이 되면 반복 종료
    elif factorization == 1:
        break
    # num을 1 증가시켜 다음 수로 넘어감
    else:
        num += 1

# 소인수들을 한 줄씩 출력
print(*prime_Factorlist, sep="\n")

https://www.acmicpc.net/problem/11653