AOJ 2858 Prime-Factor Prime

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858

解法

区間篩の要領で解ける。
[1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。
今回の場合は、素数 p が検出できたら、[L, R] には p, p^2, ... の倍数のところに1をカウントしていくことになる。
しかしこれだけだと不十分で、素因数分解でよくある （小さい素数）*（でかい素数）のでかい素数のほうがカウントされない。
なので、カウントする配列の他に、[L, R] の値を直に持っている配列を用意し、割り振るたびにその値を p で割っていくとよい。
最後に、カウンタの値と、割られて残った数が1であるか（1でないならそれも素因数なので、追加で1カウント）によって、その値が prime factor prime であるか判定する。

計算量は、篩の中で p, p^2, ... を見ていくから、結局 O(PlogRloglogP + (R - L))
（ただし、P は篩のテーブルのサイズ）で、体感はもっと早い。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    const int max_p = 1 << 18;

    int l, r; cin >> l >> r;

    vector<int> ns(r - l + 1);
    for(int i = 0; i <= r - l; ++i) {
        ns[i] = i + l;
    }
    vector<int> cnt(r - l + 1);
    vector<bool> is_prime(max_p, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i < max_p; ++i) {
        if(is_prime[i]) {
            for(int j = i + i; j < max_p; j += i) is_prime[j] = false;
            ll x = i;
            while(x <= r) {
                for(int j = (l + x - 1) / x * x; j <= r; j += x) {
                    cnt[j - l] += 1;
                    ns[j - l] /= i;
                }
                x *= i;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < r - l + 1; ++i) {
        if(ns[i] > 1) cnt[i] += 1;
        ans += is_prime[cnt[i]];
    }
    cout << ans << endl;
}