에라토스테네스의 체 (소인수분해)

struct Sieve {
    int isPrime[MAX+2];	// 소수거나 0, 1이면 -1,  합성수면 가장 작은 소인수
    void find_prime(){
        memset(isPrime, -1, sizeof(isPrime));
        int sqMAX = sqrt(MAX)+1;
        for(long long i=2; i<=sqMAX; ++i)
            if(isPrime[i] == -1)
                for(long long j=i*i; j<=MAX; j+=i)
                    if(isPrime[j] == -1)
                        isPrime[j] = i;
    }
    void print_factor(int n, vector<pii>& elem){	// 소인수 {e, k}
        elem.emplace_back(0, 0);
        while(isPrime[n] != -1){
            if (elem.back().xx == isPrime[n]) {
                ++elem.back().yy;
            } else {
                elem.emplace_back(isPrime[n], 1);
            }
            //cout << isPrime[n] << ' ';
            n /= isPrime[n];
        }
        //cout << n;
        if (elem.back().xx == n) {
            ++elem.back().yy;
        } else {
            elem.emplace_back(n, 1);
        }
        elem.erase(elem.begin());
    }
} SV;