[1Day 1Algo] 백준 11653번 소인수분해 (C++)

 

해당 문제를 보고 처음에는 "2부터 N-1까지 나눠주면 되겠지~" 라고 생각했다.

그러나 혹시 놓치고 있는 소인수분해에 대한 개념이 있을 수 있어검색을 했다.

 

눈에 띄는 부분은 소수로 자연수를 나누는 것 이었다.

 

그래서 처음 생각했던 개념을 조금 발전시켰다.

"2부터 N-1까지 소수인 수로 나눠줘야지~"

 

그리고 아래와 같은 방식으로 코드를 작성했다.

그러나 시간제한에 걸려 틀렸다.

 

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int x) {
    for (int i = sqrt(x); i > 1; i--) {
        if (x % i == 0) return false;
    }
    return true;
}

void primeFactorization(int x) {
    for (int i = 2; i <= x; i++) {
        if (!isPrime(i)) continue;
        if (x % i == 0) {
            cout << i << endl;
            primeFactorization(x / i);
            return ;
        }
    }
    return ;
}

int main() {
    int n;
    cin >> n;

    primeFactorization(n);
    return 0;
}

 

 

인터넷에 찾아보니, 꼭 나누는 수가 소수임을 검증할 필요가 없었다.

어차피 2부터 나누기 시작하기 때문이었다.

 

그래서 소수 검증 코드를 삭제하고 아래의 코드로 수정하였다.

 

#include <iostream>
using namespace std;

void primeFactorization(int x) {
    for (int i = 2; i <= x; i++) {
        if (x % i == 0) {
            cout << i << endl;
            primeFactorization(x / i);
            return ;
        }
    }
    return ;
}

int main() {
    int n;
    cin >> n;

    primeFactorization(n);
    return 0;
}