[BOJ / 파이썬] 11653번: 소인수분해

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/11653

11653번: 소인수분해

단계 : 기본 수학 2

알고리즘 분류 : 수학, 정수론, 소수 판정

 

풀이: 

 가장 작은 소수인 2부터 해당 수가 소수일 때를 가정해 해당 수를 끝으로 하는 range를 생성해 for문을 돌리며 (입력받은)숫자가 현재 for문의 숫자(i)로 나눌 수 있을 동안 해당 수를 출력하며 숫자를 해당 수로 나눈 결과로 바꿔준다. 해당 수가 1이 될 경우 종료.

 

코드

n = int(input())

for i in range(2, n + 1):
    while n % i == 0:
        print(i)
        n /= i
    if n == 1:
        break