어려운 소인수분해

백준 16563번: 어려운 소인수분해

아이디어

에라토스테네스 체 잡기술
arr[i]에 i의 가장 작은 소인수를 저장한다. 주어진 숫자 k를 저거 계속 타고가면서 나누면 소인수분해임.

아니면 루트500만까지 소수 구해놓고 그 숫자로 주어진 숫자 k 계속 나누다가 다쓰면 남은 숫자 출력.
500만까지 소수 다 구하면 TLE받음 ㅠㅠ

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 5000001;
int arr[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 1; i < MAX; i++) {
        arr[i] = i;
    }

    for (int i = 2; i < MAX; i++) {
        if (arr[i] == i) {
            for (int j = i+i; j < MAX; j+=i) {
                if (arr[j] == j) arr[j] = i;
            }
        }
    }

    int n;
    cin >> n;
    while (n--) {
        int k;
        cin >> k;
        while (k != 1) {
            cout << arr[k] << ' ';
            k /= arr[k];
        }
        cout << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 5000001;
bool arr[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    vector<int> v;

    for (int i = 2; i < 3000; i++) {
        if (!arr[i]) {
            v.push_back(i);
            for (int j =i+i; j < 3000; j+=i) {
                if (!arr[j]) arr[j] = true;
            }
        }
    }

    int n;
    cin >> n;
    while (n--) {
        int k;
        cin >> k;
        for (int x : v) {
            while (k%x == 0) {
                cout << x << ' ';
                k /= x;
            }
        }
        if (k != 1) cout << k;
        cout << '\n';
    }

    return 0;
}

여담

수학 너무 어렵다..