[Codility] Lessons11. SieveOfEratosthenes-CountSemiprimes C언어 풀이

struct Results solution(int N, int P[], int Q[], int M) {
    struct Results result;
    int* prime = (int*)calloc(N/2+1,sizeof(int));
    int* s = (int*)calloc(N+1, sizeof(int));
    
    //prime 구하기
    //소수가 아닌 수에 1을 삽입하여준다. 소수는 0이 된다.
    for(int i = 2; i+i <= N; i++){
        if(prime[i] == 0){
            for(int j = i+i; j+j <= N; j=j+i){
                prime[j] = 1;
            }
        }
    }
    
    //semiprime 구하기
    for(int i = 2; i+i <= N; i++){
        if(prime[i] == 0){
            for(int j = i; i*j <= N; j++){
                if(prime[j] == 0){
                    s[i*j] = 1;
                }
            }
        }
    }

    //semiprime 총 개수 계산
    for(int i = 1; i <= N; i++)
        s[i] += s[i-1];
    
    int* ans = (int*)malloc(sizeof(int) * M);
    
    for(int i = 0; i < M; i++){
        ans[i] = s[Q[i]] - s[P[i]-1];
    }
    
   
    result.A = ans;
    result.M = M;
    return result;
}