Lesson 9: CountSemiprimes (Count Semiprimes)

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

とりあえず、簡単な解法をでやってみましょう。まずエラトステネスのふるいでNまでの素数を全部えましょう。

そして、P[i] <= k <= Q[i]　の範囲の各kが semiprime であるかないか、この素数を使って試してましょう。

この解法では１００％の正確さ スコアがもらえますが、パフォーマンスは４０％ですね。ちょっと工夫して次の素数を定数時間で得られるようにしても、これですか。全体のスコアは66%になります。

実際にこれは、問題が要求しているO(N*log(log(N))+M)の速度の解答ではないので、当然と言えば当然です。

#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;
}


とういうことで、なにかもうちょっと速度改善のためにやらなければいけないですね。
ここで、エラトステネスのふるいのようなアルゴリズムをsemiprimeを見つけるのにも使いましょう。

簡単に言うとある素数iが見つかったとき、その倍数kのうちk/i=pが素数であれば、semiprimeですね。このとき、素数を見つける時と同じように、小さい方から調べて行けば、検索はi*iからスタートしていいですね。なぜならiより小さいpに関しては、既に以前のiを調べた時に通過しているからです。

さらに、prefix sum(Lesson 3でやりましたね）の考え方をつかって、一旦subprimeのテーブルをスキャンして、ある数iまでに出現するsubprimeの数を数えて配列semi_appearedにしまっておきましょう。こうするとsemi_appeared[10] - semi_appeared[7]とすれば、8 から10の間に現れるsubprimeの数を定数時間で得られますね。

この方針はO(N*log(log(N))+M) の時間的な複雑さになります。素数もsemiprimeもふるいのアルゴリズムでO(N*log(log(N)))ですから、このアルゴリズムに関わる部分をたすとO(N*log(log(N)) + N*log(log(N)))　=> O(2 * N*log(log(N)))で定数は無視しますから、O(N*log(log(N)))となります。

また、prefix sumをつくる部分は O(N)になりますね。これを更に足すとO(N*log(log(N)) + N)ですが、両方ともNに依存し、N*log(log(N))の方がNより大きいので、Nを無視してO(N*log(log(N))となりますね。

最後に、戻り値を計算するわけですが P[i] and Q[i]の間のsemiprimeはもう定数時間で引き算でだせることになったわけです。これをM回繰り返すのでこの部分はO(M)になりますよね。

これを先ほどまでのO(N*log(log(N))に足すとO(N*log(log(N) + M)の複雑さになり、問題の要求に合致しますね。

これで下記のように１００％のスコアがもらえました。

#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;
}