素数判定 in C/C++

エラトステネスの篩は以前に書いたのだが、このアルゴリズムはある1つの数が素数かどうかを判定するには向いていない。

今回は、試し割りによって数nの素数判定を行う関数bool is_prime(const unsigned n)を実装する。

愚直な実装

bool is_prime(const unsigned n){
    switch(n) {
        case 0: // fall-through
        case 1: return false;
    } // n > 1 が保証された

    // n より小さい数で n を割って余りを調べる
    // 素数ならば自分より小さい数(1以外)では割り切れない
    for(unsigned i = 2; i < n; ++i) {
        if(n % i == 0) return false;
    }

    return true;
}

「愚直な実装」の問題点

・2～n-1まで試し割りしているが、実は2～$\sqrt{n}$で十分
・奇数・偶数問わず試し割りしているが(2以外の)偶数は素数ではないので、実は奇数のみで試し割りすればよい。

修正した実装

bool is_prime(const unsigned n){
    switch(n) {
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
    } // n > 2 が保証された

    if(n % 2 == 0) return false;

    // 上で i=2 相当は調べたので、i=3から奇数のみ調べる
    for(unsigned i = 3; i * i <= n; i += 2) {
        if(n % i == 0) return false;
    }

    return true;
}

より良い実装

3以上の素数は、6で割ったときの余りが1か5になる¹。
別の言い方をすると、3以上の素数は6の倍数の前後にのみ存在する。

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n % 2 == 0 || n % 3 == 0) return false;
    // n は 2 と 3 のいずれの倍数でもないことが保証された
    // これより n は (6の倍数)-1 か (6の倍数)+1 である

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }

    return true;
}

6は素数である2と3の積なのでこんなことができる。
次の素数である5を更にかけると30になるが、30で割った余りは役に立つようには思えない。
素数となる数の候補が多すぎるのだ。
$(30n+1,30n+7,30n+11,30n+13,30n+17,30n+19,30n+23,30n+29)$

---

1. 自然数 $n$ を用いて、任意の自然数は$6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5$のいずれかとして表現できる。このうち、$6n$は6の倍数、$6n+2, 6n+4$は2の倍数、$6n+3$は3の倍数なので、素数である可能性があるのは$6n+1, 6n+5$のみ ↩