[백준 11653] 소인수분해

🔗알고리즘 문제

기존의 소수 문제와 똑같이 먼저 소수를 구한뒤에 소수로 나눠주는 작업을 해야겠다 ! 라고 생각했지만 무수한 실패와 시간초과를 경험하고 도저히 생각이 안난다 싶어서 다른 사람의 코드를 조금 참고하여 푼 문제이다.

문제 분석

문제에 나온 그대로 정수 n이 주어졌을 때 이를 소인수분해한 결과를 출력하는 문제이다.

발상 & 알고리즘 설계

처음에는 해당 수 까지의 소수를 모두 구한 뒤에 각각의 소수로 나눈 후 결과를 출력하려고 하였다.

하지만 생각해보면 소인수분해란 단지 그 수가 소수로 나눠지지 않을때까지 소수로 나누는것이다.

이를 깨달은 후 쉽게 문제를 해결할 수 있었다.

코드

#include<iostream>

using namespace std;

int main(){
    int n;

    cin >> n;

    while(n > 1){
        for(int i = 2; i <= n; i++){
            if(n % i == 0){
                cout << i << endl;
                n /= i;
                break;
            }
        }
    }
}