エラストテネスと間違っていた時代もありました

awk


では 2 つめのエラトステネスの篩です。エラトステネスの篩 - Wikipedia を見て作ったのが、こちらです。

#! /usr/bin/gawk -f
# eratosthenes2.awk - get prime numbers (from 1 to ARGV[1])
# usage: gawk -f eratosthenes.awk
#   input:  max numbers (ARGV[1])
#   output: prime numbers

BEGIN {

    num = ARGV[1];

    for (i = 2; i <= num; i++) {
        num_arr[i] = i;
        for (j = 2; j <= num; j++) {
            if (num_arr[i] % j == 0 && num_arr[i] != j) {
                num_arr[i] = 0;
            }
        }
    }
    for (i = 2; i <= num; i++) {
        if (num_arr[i] != 0) {
            print num_arr[i];
        }
    }
}

1 から (2 からでも同じですが) を順々に篩から落としていきます。指定は調べたい最大の数を ARGV[1] で指定します。

$ gawk -f eratosthenes2.awk 25
2
3
5
7
11
13
17
19
23

一方、「C言語による最新アルゴリズム事典」では 2 を特別扱いにして、篩の目を最適化しています。また、指定は個数に変わりますが、以下のようなものです。

#! /usr/bin/gawk -f
# eratosthenes.awk - get prime numbers (mumbers of ARGV[1])
# usage: gawk -f eratosthenes.awk
#   input:  numbers of ARGV[1]
#   output: prime numbers

BEGIN {

    num = ARGV[1];

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

結果は以下のようになります。(2 が表示されませんが、そう組んでいますから、それで正解です)

$ gawk -f eratosthenes.awk 10
3
5
7
11
13
17
19
23

前者は 1 年くらい前に私の頭をダンプしたもので、小飼さんに指摘されたメモワイズのようなものを使っています。多分、私の頭のメモって、非効率だなぁと感じるところでもあります。

え〜っと、次は「二分探索」ですかね。良い例が思いついていませんが、大学時代の流体力学を二分探索で、しかも Lotus 1-2-3 で解いた記憶がありますが、ここの例ではふさわしくないので、何か探してみます。

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)