R6秋 応用情報午後 プログラミングを検証

いざ、検証！

prime1(20),prime2(20),prime3(20)をそれぞれ実行したときのL1,L2,L3の実行回数を検証します。

コード

r6a.c

#include <stdio.h>

int L1 = 0;
int L2 = 0;
int L3 = 0;

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++; // <---------------------(L1)
            L1++;
        }
        if(isPrime == 1){
            primes[i++] = d;
        }
        d++;
    }

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

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; // <---------------------(L2)
                L2++;
            }
        }
        d++;
    }

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

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; // <---------------------(L3)
                L3++;
            }
        }
        d += 2;
    }

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

int main() {
    int N = 20;
    int primes[N];
    int count;
    
    int* prime_list1 = prime1(N, primes, &count);
    int* prime_list2 = prime2(N, primes, &count);
    int* prime_list3 = prime3(N, primes, &count);

    printf("%d, %d, %d\n", L1, L2, L3);
    return 0;
}

実行結果

171, 13, 2

時間計測（ナノ秒）

ヘッダーファイルをインクルードして

#include <time.h>

main関数を以下に書き換えて実行。なお、実行時間はマイクロ秒以下のため、time()やclock()だと0になってしまう。

int main() {
    int N = 20;
    int primes[N];
    int count;
    struct timespec start, end;
    
    timespec_get(&start, TIME_UTC);
    int* prime_list1 = prime1(N, primes, &count);
    timespec_get(&end, TIME_UTC);
    printf("prime1:%ld\n", end.tv_nsec - start.tv_nsec);
    
    timespec_get(&start, TIME_UTC);
    int* prime_list2 = prime2(N, primes, &count);
    timespec_get(&end, TIME_UTC);
    printf("prime2:%ld\n", end.tv_nsec - start.tv_nsec);
    
    timespec_get(&start, TIME_UTC);
    int* prime_list3 = prime3(N, primes, &count);
    timespec_get(&end, TIME_UTC);
    printf("prime3:%ld\n", end.tv_nsec - start.tv_nsec);

    return 0;
}

出力結果 (paiza.io)

prime1:392
prime2:128
prime3:30

もちろん、実行ごとに値は変わるが、だいたいこんな感じになった。
N = 100とかにすると、Bus error (core dumped)となってしまった。
本当は大きい数で試すほうが正確ではある。