StrongPrimePower.cpp

using ll = long long;
const size_t bssize = size_t(1e9);
typedef bitset<bssize> bs_t;
ll sz;

class StrongPrimePower {
    public:
        set<int> S;
        bs_t *P = new bs_t();//better have smart ptr to deal with resource recycle

        void sieve(ll upperbound){
            sz = upperbound;
            P->set();
            P->reset(0);
            P->reset(1);
            for(ll i=2;i<sz;++i){//generating prime < 10^9
                if(P->test(i)) {
                    S.insert(i);
                    for(ll j=i*i;j<sz;j+=i){
                        P->reset(j);
                    }
                }
            }
        }

        bool isPrime(ll n){
            if(n<sz){
                return P->test(n);
            }
            for(int pr:S){
                if(n%pr==0){
                    return false;
                }
            }
            return true;
        }


    vector<int> baseAndExponent(string n) {
        sieve(1e9);
        ll num = stoll(n);
        if(isPrime(num)) return vector<int>();
        delete P;

        for(int pr:S){
            int q=0;
            ll p=num;
            while(p%pr==0){
                q++;
                p/=pr;
                if(p==1) return {pr, q};
            }
        }
        return vector<int>();
    }
};