[백준] 11653 - 소인수분해

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

11653번: 소인수분해

n을 입력받고 이를 sqrt(n) 까지 소수로 나눠줍니다. 나눠줄 수 num을 2부터 시작해 나눠지지 않거나 소수가 아니면 1씩 더해줍니다. 그리고 소수판정 시에도 sqrt(num) 까지 해주고 소수로 판정되면 visit 배열로 체크해 다음부턴 판정하지 않도록 합니다. 마지막에 n이 1이면 다 나누어 떨어진 것이고 1이 아니면 마지막 소수가 되니 출력해 줍니다.

 

#include <iostream>
#define MAX 3200
using namespace std;

bool visit[MAX] = { false };

bool isPrime(int x) {
    bool flag = true;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int num = 2;
    while (n != 1) {
        if (num * num <= n) {
            if (!visit[num]) {
                if (isPrime(num))
                    visit[num] = true;
                else
                    num++;
            } else {
                if (n % num == 0) {
                    n /= num;
                    cout << num << "\n";
                } else {
                    num++;
                }
            }
        } else break;
    }

    if (n != 1)
        cout << n << "\n";

    return 0;
}