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

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

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

単純な方法

prime1.c

#include <stdio.h>

int* prime1(int N, int primes[], int* count){
    int i = 0;  // primesの末尾インデックス
    int isPrime; // 1:True(prime), 0:False(not prime)

    int d = 2;
    int t;
    while(d <= N){
        isPrime = 1; // True, 素数と仮定
        t = 2;
        while(t < d){
            if(d % t == 0){
                isPrime = 0; // False
            }
            t++;
        }
        if(isPrime == 1){
            primes[i++] = d;
        }
        d++;
    }

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

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

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

    return 0;
}

実行結果

2 3 5 7 11 13 17 19 

外側のwhile: d = 2 ~ N
内側のwhile: d = 2のとき0回, d = 3のとき1回, d = 4のとき2回,...,d = N-1のときN-3回
-> $0 + 1 + 2 + ... + N-3 = \frac{(N-3)(N-2)}{2} = N^2-5N+6 $
-> $O(N^2)$

関数prime1の時間計算量は$O(N^2)$となります。