백준 문제 풀이 - 소인수분해 11653번

📜 문제 이해하기

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

💡 문제 재정의

N의 소인수를 출력하기

✏️ 계획 수립

1. N을 2부터 N까지 나눠떨어지는지 확인한다.
2. 나눠떨어진다면 나누는 값을 출력하고 N에 몫을 집어넣는다.
3. 나누어떨어지지 않는다면 나누는 값을 1씩 올린다.
4. 위 과정을 N이 1이 될때까지 반복한다.

💻 계획 수행

if __name__ == '__main__':
    n = int(input())
    cnt = 2
    while n > 1:
        if n % cnt == 0:
            n = n // cnt
            print(cnt)
        else:
            cnt += 1

🤔 회고

소인수분해는 위 과정으로 간단히 풀었다.
위 과정은 O(N)으로 시간이 많이 들지만 간단하다는 장점이 있다. 시간을 더 아끼기위한 더 좋은 방법이 있을 것 같다.