R6秋 応用情報 午後プログラミング2

応用情報のプログラミング問題

素数を列挙するアルゴリズムの実装です。ここでは、20以下の素数とします。
Cなので、関数で配列を直接返せないので、問題のものからいくつか変数を追加しています。

改良1

単純な方法だと計算量は$O(N^2)$でした。
素数の定義によって、2以上の自然数sについて、s自身を除くsの正の倍数uは、1とu以外にsも約数に含むので素数ではありません。この性質を利用したのが関数prime2です。

prime2.c

#include <stdio.h>

int* prime2(int N, int primes[], int* count){
    int i = 0;  // primesの末尾インデックス
    int isPrime[21] = {0};

    int c = 2;
    int d = 2;
    int t;
    while(c <= N){
        isPrime[c] = 1;
        c++;
    }
    while(d <= N){
        if(isPrime[d] == 1){
            primes[i++] = d;
            t = d * d;
            while(t <= N){
                isPrime[t] = 0;
                t += d;
            }
        }
        d++;
    }

    *count = i;  // 素数の個数をカウント
    return primes;
}

int main() {
    int primes[20];
    int count;
    int* prime_list = prime2(20, primes, &count);

    // 素数のリストを表示
    for (int i = 0; i < count; i++) {
        printf("%d ", prime_list[i]);
    }
    printf("\n");

    return 0;
}

dが素数なら、次はt = d * d;が実行されます。d = 2のときt = 4, d = 3のときt = 9です。間の5,6,7,8のうち、5,7は素数だからいいとして、6,8については、d = 2のときFalseになるので非素数として記録されます。

当初、なぜ、t = d + d;ではないのか悩んだのですが、よく考えるとprime2は成り立つことがわかります。これにより、prime1よりも少ない計算量で済みます。