[수학/소수] 백준 11653 소인수분해 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11653번: 소인수분해

 

 

 

2. 문제 풀이

 주어진 N을 소인수분해 하는 문제입니다.

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 에라토스 테네스의 체처럼, 2부터 나누는 수를 1씩 올려가며 N의 약수인지 확인합니다. 나눠지는 수는 굳이 소수판별을 하지 않아도 '소수'입니다.

 에라토스 테네스의 체의 원리와 마찬가지로, 소수의 배수들은 약수가 될 수 없기 때문입니다. 1씩 올리며 자기 차례가 되었을 때 나눠진다면, 해당 수는 소수입니다.

 

 

 

3. 코드

N = int(input())

divided = 2 #나누는 수
while N != 1: #약수로 나눠서 1이 될 때까지 반복
    if N % divided == 0: #나누어질 경우
        print(divided) #약수 출력
        N //= divided #약수로 나누기
        divided = 1 #나누는 수 초기화
    divided += 1

 약수를 발견했다면, 다시 2부터 1씩 올리며 약수를 찾습니다.