【典型90問】030 - K Factors（★5）

atcoder.jp

解法

エラトステネスの篩で素数かどうか判定する代わりに、素因数の種類を数えればOK。
N ≦ 10⁷ でも間に合うんですね。

実装

K=1のときは場合分けした方が実装が楽だと思った。

void solve(long long N, long long K) {
    if (K == 1) {
        c(N-1)
        return;
    }

    // 素因数の種類がいくつか
    vector<int> fac(N, 0);
    // エラトステネスの篩
    int ans = 0;
    for (int i = 2; i <= N; i++) {
        if (fac[i] >= K) ans++;
        if (fac[i]) continue;

        for (int j = i; j <= N; j += i) fac[j]++;
    }

    c(ans)
}