区間篩

e(L,R)でLからRまでを全て素因数分解する

計算量はNloglogNとかになるらしい

vector<vector<pair<long long,long long>>> e(long long l,long long r){
    vector<bool> b(sqrtl(r)+3,true);
    vector<long long> so;
    for(long long i = 2;i < b.size();i++){
        if(b[i])so.push_back(i);
        for(long long j = i+i;j < b.size();j+=i){
            b[j] = false;
        }
    }
    vector<long long> v;
    for(long long i = l;i <= r;i++)v.push_back(i);
    vector<vector<pair<long long,long long>>> ans(v.size());
    for(long long i : so){
        for(long long j = max(i,((l+i-1ll)/i))*i;j <= r;j+=i){
            int J = j-l;
            long long cnt = 0;
            while(v[J]%i==0){
                v[J]/=i;
                cnt++;
            }
            if(cnt!=0)ans[J].push_back({i,cnt});
        }
    }
    for(long long i = 0;i < v.size();i++){
        if(v[i]!=1)ans[i].push_back({v[i],1});
    }
    return ans;
}

区間篩を用いた素因数の種類数のカウント

e(L,R)でL〜Rまでの数のやk数の個数を列挙する

vector<long long> e(long long l,long long r){
    vector<bool> b(sqrtl(r)+3,true);
    vector<long long> so;
    for(long long i = 2;i < b.size();i++){
        if(b[i])so.push_back(i);
        for(long long j = i+i;j < b.size();j+=i){
            b[j] = false;
        }
    }
    vector<long long> v;
    for(long long i = l;i <= r;i++)v.push_back(i);
    vector<long long> ans(v.size());
    for(long long i : so){
        for(long long j = max(i,((l+i-1ll)/i))*i;j <= r;j+=i){
            int J = j-l;
            long long cnt = 0;
            while(v[J]%i==0){
                v[J]/=i;
                cnt++;
            }
            if(cnt!=0)ans[J]++;
        }
    }
    for(long long i = 0;i < v.size();i++){
        if(v[i]!=1)ans[i]++;
    }
    return ans;
}