エラトステネスの篩で素数を求める

素数を求めるアルゴリズム -エラトステネスの篩（ふるい）- - forest book にインスパイヤされて、エラトステネスの篩で素数を求めてみます。 エラトステネスの篩 - Wikipedia に書かれているように篩で素数でないものを落としていき、最後に残ったものが素数になるというものですが、Amazon.co.jp： C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー): 奥村 晴彦: 本に書かれてある篩は非常にスマートになっています。 また、2 は特別扱いにすることで高速化を行っています。

#! /usr/local/bin/nawk -f
# eratosthenes_3.awk
# エラトステネスの篩で素数判定を行う
# usage: nawk -f eratosthenes_3.awk num

BEGIN {
    num = (ARGV[1] - 3) / 2;

    printf("2 ");

    for (i = 0; i <= num; i++) {
        flag[i] = 1;
    }

    for (i = 0; i <= num; i++) {
        if (flag[i] == 1) {
            p = i + i + 3;
            printf("%d ", p);

            for (k = i + p; k <= num; k += p) {
                flag[k] = 0;
            }

        }
    }

    print "";
}

これにより第 1 引数までの素数を高速に数え上げることができます。

$ nawk -f eratosthenes_3.awk 10
2 3 5 7

$ nawk -f eratosthenes_3.awk 100
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

キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ring で取り上げられたことで、様々なアルゴリズムが紹介された中でもエラトステネスの篩はよく使われていたアルゴリズムです。