Prime numbers sieve C言語化編

2023年1月3日 13:49

先日、こちらの記事で素数生成イテレータを紹介しました。 Python ドキュメントにあったチュートリアルを解説したものです。

最後にこう書きました。

「C言語で書くとどうなるかしら」

というわけで、C言語で書いてみた。

コード

#include <stdio.h>
#include <stdbool.h>

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

int iter_primes(int prime)
{
    prime++;
    while (!is_prime(prime))
    {
        prime++;
    }
    
    return prime;
}

int main()
{
    int prime = 2;
    while (prime < 1000)
    {
        printf("%d\n", prime);
        prime = iter_primes(prime);
    }
    
    return 0;
}

実行結果

解説

うーん。
なんとなく、あんまり上手くはいかないかな。

関数「iter_primes」

関数「iter_primes」は、「イテレータ」と銘打っているものの、単に引数「prime」の次の素数を返すというだけの関数に過ぎない。関数内部で static に素数を持とうかと思ったんだけど、そうするとリセットするタイミングが必要だし、この関数ではリセットのタイミングはわからないし、それじゃあ引数で教えてあげなきゃいけないわけで、なんだかんだでこんなになった。

関数「is_prime」

関数「is_prime」も総当たりチェックだしね。
既に判定済みの素数リストを作っていけばチェックする回数も減らすことができるだろうけど、減る回数とプログラムの複雑さとを天秤にかけてどちらが効率的なのか判断が付かずこのままとした。

bool 型

関数「is_prime」の型を「bool」にしてみた。昔は bool 型はなかったけど、「#include <stdbool.h>」で使えるらしい。ただ、この「bool」、「#define bool _Bool」としただけ。なので「undef」もできる。C99 で追加されたそうだけど、それまでにプログラマーが my bool を定義し続けてきたので、言語仕様レベルに強制的に移行するのは難しかったよう。

この記事が気に入ったらサポートをしてみませんか？