Prime-Factor Prime [JAG Practice Contest for ACM-ICPC Asia Regional 2017 C]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_c

[L,R]の数で素因数分解したときの素因数の個数(同じ素因数でも重複して数える)が素数の数は何個？

前提知識

• 区間篩

解法

https://jag2017autumn.contest.atcoder.jp/submissions/1794378

条件でR-L＜10^6というのは結構珍しい。
この条件が出て素因数分解と来たら区間ふるいをまず思い浮かべよう。
　
区間篩の特徴的な所は部分的にエラトステネスの篩をやることである。
最大が10^9なので、4*10^4以下の素数を予め用意しておく。
素因数分解を区間に対して一気にやるのだが、例えば素数pである数xが割れたとする。
すると、x+1やx+2は割れないので無視してよく、次に考えるべきはx+pの数となる。
よって、各素数について最初の位置が分かれば次の位置は飛ばして考えることができるのである。
これをやっていくだけなのだが、倍数だけ考えるこの手法はNlogNで行えることが知れているので、それを使う。
あとは、素因数をカウントした配列に対して素数判定をして、答えを数え上げる。

int L, R;
int A[1010101];
int cnt[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L >> R;
 
    vector<int> primes = makePrimes(40101);
 
    rep(i, L, R + 1) A[i - L] = i;
    fore(p, primes) {
        for (int l = (L + p - 1) / p * p; l <= R; l += p) {
            while (A[l - L] % p == 0) A[l - L] /= p, cnt[l - L]++;
        }
    }
 
    rep(i, 0, R - L + 1) if (1 < A[i]) cnt[i]++;
    int ans = 0;
    rep(i, 0, R - L + 1) {
        if (isprime(cnt[i]) and 0 < cnt[i]) ans++;
    }
    cout << ans << endl;
}