11653번: 소인수분해

문제

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

아이디어

소인수분해 알고리즘 → 클릭
속도를 빠르게 하려면? if문 추가

코드

파이썬 - while문 ver. (228초)

python

import sys
input = sys.stdin.readline

n = int(input())
d = 2
while True:
    if n == 1:
        break
    if n % d == 0:
        n //= d
        print(d)
    else:
        d += 1

파이썬 - for문 ver. (초)

python

n = int(input())
if n == 1:
    print('')

# 2부터 하나씩 나눠보기
for i in range(2, n+1):
    if n % i == 0:
    	#해당 숫자로 나눌 수 없을 때까지 나누기
        while n % i == 0:
            print(i)
            n = n / i