[Baekjoon] 11653 소인수분해

[Silver V] 소인수분해 - 11653

문제 링크

성능 요약

메모리: 12896 KB, 시간: 144 ms

분류

수학(math), 정수론(number_theory), 소수 판정(primality_test)

문제 설명

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

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

알고리즘

소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 
소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는
방법을 말한다.

출처 : 위키백과

위에 소인수분해의 정의를 써 놓았다.

쉽게 말하면 그냥 1을 제외한 소수의 곱으로 나타내는 것이다.

항상 백준을 풀 때 아직 내가 알고리즘을 제대로 배우지 않아서 이렇게 푸는 게 맞나 싶긴하다.

최대한 간단한 방법을 생각하다보니 전에 풀었던 소수 구하는 예제를 응용하여 prime[] 배열을 사용하려다가 그냥 없이 풀어보기로 하였다.

이번 문제의 내가 생각한 알고리즘은 이렇다.

그냥 for()문을 사용하여 2부터 N까지 전부 나눠준다고 생각했다.

하지만 이렇게 하니 문제가 하나 있었다.

아래 코드에 주석에도 달아놓았지만 그냥 for()문을 돌릴 경우 소인수 분해에서 만약 2로 나누고 2로 더 나눌 수 있는 경우가 생겨도 3으로 넘어가버리는 경우가 생긴다.

그래서 이 문제를 나는 i--;를 통해 2로 나누고 다시 2를 확인하거나 3으로 나누고 다시 3을 확인하는 방식으로 문제를 풀었다.

다른 좋은 방법이 많이 있는 것 같지만 내가 푼 방법은 이렇게 간단하게 끝이 났다.

---

코드