[백준/BOJ] 11653. 소인수분해 (C++)

문제

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

 

풀이

2로 나눈 나머지가 0인 동안, 2로 나누고 2 출력

2로 나눈 나머지가 0이 아닐 경우, 2 → 3

 

3으로 나눈 나머지가 0인 동안, 3으로 나누고 3 출력

3으로 나눈 나머지가 0이 아닐 경우, 3 → 4

 

...

 

i로 나눈 나머지가 0인 동안, i로 나누고 i 출력

i로 나눈 나머지가 0이 아닐 경우, i++

 

=> i 가 N보다 작거나 같은 동안 실행.

 

소스코드

#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    int i=2;
    // i로 나눠지지 않을 때까지 i로 나누고 i 출력.
    // 나눠지지 않으면 i = i+1
    while(i <= N)
    {
        if(N%i == 0) {
            cout << i << endl;
            N = N / i;
        } else {
            i = i+1;
        }
    }
    
    return 0;
}

회고

뭔가 수학적 지식이 필요할 것 같았던 문제 이름에 비해 쉽게 풀렸다.

 

무작정 i 다음에 i+1을 하기보다 (4를 건너뛰는 등) 소수만 확인해보는 방법은 없을까 ?