Lesson 9: CountSemiprimes - (Count Semiprimes)

Lesson 9: CountSemiprimes
https://codility.com/programmers/lessons/9

First, let's implement a simple solution. 
We use Sieve of Eratosthenes to find prime numbers less than and equal to N.

Then we check each k (P[i] <= k <= Q[i]) is a semiprime or not
by using these prime numbers one by one.

This solution gives the 100% correctness score, but the only 40% performance score. Even when we use some strategy to pick up the next prime number quickly, the overall score given is only 66%.

Indeed, this is not a solution with the O(N*log(log(N))+M) time complexity that the problem requires, so this score is fair.

#include<alloca.h>
#include<memory.h>

int check(int k, int N, char* sieve, int* next_prime)
{
    //if k is less than 4 or a prime number,
    //it is never a semiprime
    if (k < 4 || sieve[k] == 1){
        return 0;
    }
    //check if k is a semiprime.
    int num = 2;
    while (num * num <= k){
        num = next_prime[num];
        if (k > num && k % num == 0 && k / num <= N && sieve[k / num] == 1){
            return 1;
        }
        num++;
    }
   
    return 0;
}

struct Results solution(int N, int P[], int Q[], int M)
{  
    //compute the prime number
    int size = sizeof(char) * (N + 1);
    char* sieve = (char*)alloca(size);
    memset(sieve, 0x01, size);
   
    int i, j, k;
    i = 2;
    sieve[0] = sieve[1] = 0;
    while(i * i <= N){
        if (sieve[i]){
            k = i * i;
            while(k <= N){
                sieve[k] = 0;
                k += i;
            }
        }
        i++;
    }
   
    //the next prime number
    int* next_prime = (int*)alloca(sizeof(int) * (N + 1));
    next_prime[N] = sieve[N] == 1 ? N : -1;
   
    for (i = N - 1; i >= 0; i--){
        if (sieve[i]){
            next_prime[i] = i;
        }
        else {
            next_prime[i] = next_prime[i + 1];
        }
    }

    struct Results result;

    result.A = (int*)malloc(sizeof(int) * M);
    result.M = M;


    //start finding semiprime for each.
    for (i = 0; i < M; i++){
        int cnt = 0;
        for (j = P[i]; j <= Q[i]; j++){
            if (check(j, N, sieve, next_prime)){
                cnt++;
            }
        }
        result.A[i] = cnt;
    }


    return result;
}




So now it is clear that we have to do some trick. Let's use the sieve algorithm also to find semiprime numbers. Then use the prefix sum of the occurrence of semiprime numbers from 0 to N, so that we can count the number of semiprime numbers in a constant time.

This strategy gives the O(N*log(log(N))+M) time complexity. As the sieve algorithm is used both for finding prime numbers  and subprime numbers, These parts have the O(2* N*log(log(N))) => O(N*log(log(N))) time complexity. 

The part to make an array of prefix sum is the O(N) time complexity. Then so far, it is still O(N*log(log(N)) + N) => O(N*log(log(N)). 

To compute the return value, as the number of semiprime between P[i] and Q[i] can be found in a constant time and we repeat it M times, the time complexity will be O(M).

Adding this to O(N*log(log(N)), the O(N*log(log(N) + M) time complexity is what we have in this solution.

As below, this solution gives the 100% score.

#include <alloca.h>
#include <memory.h>

struct Results solution(int N, int P[], int Q[], int M)
{  
    //compute the prime number
    int size = sizeof(char) * (N + 1);
    char* sieve = (char*)alloca(size);
    memset(sieve, 0x01, size);
   
    int i, j, k;
    i = 2;
    sieve[0] = sieve[1] = 0;
    while(i * i <= N){
        if (sieve[i]){
            k = i * i;
            while(k <= N){
                sieve[k] = 0;
                k += i;
            }
        }
        i++;
    }
   
    //make the semiprime number table.
    size = sizeof(char) * (N + 1);
    char* semiprime_table = (char*)alloca(size);
    memset(semiprime_table, 0x00, size);

    i = 2;
    while(i * i <= N){
        //we care only about prime numbers.
        if (sieve[i] == 0){
            i++;
            continue;
        }
        
        k = i;
        while(k * i <= N){
            if (sieve[k] == 1){
                semiprime_table[k * i] = 1;
            }
            k++;
        }
        i++;
    }
    
    //the number of the semiprime number appered until the index.
    int* semi_appeared = (int*)alloca(sizeof(int) * (N + 1));
    semi_appeared[0] = 0;
    for(i = 1; i <= N; i++){
        semi_appeared[i] = semi_appeared[i - 1] + semiprime_table[i];
    }

    struct Results result;

    result.A = (int*)malloc(sizeof(int) * M);
    result.M = M;

    for(i = 0; i < M; i++){
        result.A[i] = semi_appeared[Q[i]] - semi_appeared[P[i] - 1];
    }

    return result;
}