[Codility] CountSemiprimes C++

세미프라임은 처음듣네........

그냥 프라임 구하고

세미프라임 구해서

dp만들어서 해줬다.

vector<int> primeNum;
int arr[50001] = {0,};

void semiprime(){
    for(int i=0; i<primeNum.size(); i++){
        for(int j=i; j<primeNum.size(); j++){
            if((long long)primeNum[i]*primeNum[j]>50000)   break;
            int n = primeNum[i]*primeNum[j];
            arr[n]++;
        }
    }
}

void prime(){
    for(int i=2; i<50001; i++){
        bool flag = true;
        for(int j=2; j*j<=i; j++){
            if(i%j==0){
                flag = false;
                break;
            }
        }
        if(flag){
            primeNum.push_back(i);
        }
    }
}

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {
    prime();
    semiprime();
    vector<int> v;
    int dp[50001] = {0,};
    for(int i=2; i<50001; i++){
        dp[i] = dp[i-1]+arr[i];
    }
    for(int i=0; i<P.size(); i++){
        v.push_back(dp[Q[i]]-dp[P[i]-1]);
    }
    return v;
}