C言語勉強ノート　（Prime numbers sieve C言語化編）

Ayumiさんによるプログラミング解説記事「Prime numbers sieve」。

素数を求めるプログラムをPythonで解説されていたのですが、私がPythonに対する知見が全くゼロのため着いていくいけずに断念。

ところが、C言語編を公開していただいたので、早速チャレンジしてみました😆

改めて、素数とは？

2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。

https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

トライアル

引数が素数であるかどうかを判断するis_prime関数は、Ayumiさんのコードを流用しています。与えられた引数が素数であるかどうかを、2, 3, 4,,,と順番に、引数の半分に達する数値でまで割ってみて、どの数値でも割り切れなかったら（余りが出たら）素数であると判断します。

成る程。

先人のロジックを解析して、新しい知識を得る。
自分でもそのロジックを使ってみて、理解を深める。

楽しい。

/* main.c */ 
#include <stdio.h>
#include <stdbool.h>

int counter = 0;
bool is_prime(int number)
{
    int i;
    for (i = 2; i <= (number/2); i++)
    {
        counter++;
        if ((number % i) == 0) {return false;}
    }

    return true;
}

int main()
{
    int cnt, indx = 0, prime_table[1000] = {0};

    for (cnt = 2; cnt < 1000; cnt++) {
        if (is_prime(cnt)) {
            prime_table[indx] = cnt;
            indx++;
        }
    }

    indx = 0;
    while (prime_table[indx] != 0){
        printf("%d\n", prime_table[indx]);
        indx++;
    }

    printf("counter = %d\n", counter);
    return 0;
}

実行結果

Ayumiさんのと同じ結果が得られました。先ずはオッケーのようです。

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997
counter = 40042

プログラミング談議

ここまで出来たら、早速Ayumiさんに報告です。

コメント欄にコードを載せるというアナーキーさ！

23時過ぎにメッセージを送ったら、なんとその日のうちにバグを指摘する返信を戴きました。

さすがです。

Ayumiさんもコメント欄でコードを公開。ますますアナーキーな雰囲気になってきました。

「素数リストを作ってチェック回数を減らしてみました」？？？

私には、仰っている意味がわからない。
早々にギブアップ。

、、、全コードを開示して頂いて、やっと意味がわかりました。
（Ayumiさんの記事のコメント欄に掲載されています）

よくよく考えてみれば、
２で割り切れないものは、４でも６でも割り切れないし、
３で割り切れないものは、６でも９でも割り切れない。
総当たりで割り算して剰余を計算するのではなく、それまでに判明している素数で割れば良い。そういうことです。
当初のコードでは、随分と無駄なテストをしていたようです。

prime_check = 15813

私のコードだと、引数が素数であるかどうかを判断するis_prime関数を40042回も実行しているのに、Ayumiさんのコードだと15813回で済んでいます。これはかなり、パフォーマンスを改善していますね。

プログラミングって、こういうところが実に奥が深くて面白い。
適当なコードで、あとはCPUパワーでレスポンスをカバーするというのもありと言っちゃありですが、無駄を削ぎ落としつつ、例外処理を排除して汎用性を上げるという二律背反的なものを求めるチューニング作業が実に楽しい。

Ayumiさん、私の無茶ぶりにお付き合い戴き、有難うございました。
今後とも宜しくお願いします。

ここまで読んでいただき、有難うございました。

追記：2023年１月9日

公式（Ayumiさん）から解説が発表されました。ふむふむ。

続編がリリースされました: 2023年1月21日

公式（Ayumiさん）から解説の続編が発表されました。こちらも要チェック！