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

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

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

改良2

4以上の偶数は全て2の倍数であるので、素数ではありません。よって、2以外の素数は奇数となります。これを利用したのが関数prime3です。

prime3.c

#include <stdio.h>

int* prime3(int N, int primes[], int* count){
    int i = 0;  // primesの末尾インデックス
    primes[i++] = 2; // 素数2を格納
    int isPrime[21] = {0};

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

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

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

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

    return 0;
}

余談ですが、cindex = 0;だと、最後の素数が出ないという結果になったのですが、cindex = 1;にすると、修正できました。
問題文中のインデックスが$1$始まりなので、地味に頭の中がややこしくなります。