atcoder.jp 解法 エラトステネスの篩で素数かどうか判定する代わりに、素因数の種類を数えればOK。 N ≦ 107 でも間に合うんですね。 実装 K=1のときは場合分けした方が実装が楽だと思った。 void solve(long long N, long long K) { if (K == 1) { c(N-1) re…