백준 11653 - 소인수분해

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

11653번: 소인수분해

import sys

input = sys.stdin.readline

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

n을 입력받고 n이 1이 될 때까지 반복해서 2이상의 수로 나누는 방식이다. brute force하게 하나하나 일일이 다 대입해보는 형태의 코드로 작성했는데, 맞긴 했지만 속도가 느리다.

n = int(input())
i = 2
r = int(n ** 0.5)

while i <= r:
    while not n % i:
        print(i)
        n //= i
    i += 1
if n > 1:
    print(n)

다른 사람의 코드인데, 에라토스테네스의 체를 활용해서 입력받은 수의 제곱근까지만 반복해서 반복의 횟수를 n**0.5로 줄인 좋은 코드다.