SRM 442 UnderPrimes

A <= x <= Bをみたし、かつ、xの素因数の数が素数であるxを数える。
→問題についてはこちらの方のブログを見てください。
http://topcoder.g.hatena.ne.jp/namakemono_srm/20111017/1318834809

高速な解法
まず素数をふるって求める。
その後DPで素因数の数を数える。
最悪ケースでも4ms

const int M = 100010;
bool isPrime[M] = {false};
vector<int> counts(M);
vector<int> primes;

class Underprimes {
    public:

    void sieve(){
        for(int i=2;i<M;i++) isPrime[i] = true;
        for(int i=2;i*i<M;i++){
            if(!isPrime[i]) continue;
            for(int j=i*i;j<M;j+=i){
                isPrime[j] = false;
            }
        }
        for(int i=2;i<M;i++) if(isPrime[i]) primes.push_back(i);
    }
    void countup(){
        for(int i=2;i<M;i++){
            if(isPrime[i]) counts[i] = 1;
            for(int j=0;j<primes.size();j++){
                if(i*primes[j] < M){
                    counts[i*primes[j]] = counts[i]+1;
                }else{
                    break;
                }
            }
        }
    }

    int howMany(int A, int B) {
        sieve();
        countup();
        int ret = 0;
        for(int i=A;i<=B;i++){
            if(isPrime[counts[i]]) ret++;
        }
        return ret;
    }
};