アルゴリズム入門(素数)

素数は、1とその数以外に約数を持たない数のことです。
ある数が素数かどうかを判定するには、約数の個数を調べます。
約数は、その数以下の自然数で割って、割り切れるか調べると求められます。
「10」の約数を見つけるには、1から順に10まで割ってみればいいのです。
10 ÷ 1 = 10 あまり 0 → 割り切れる
10 ÷ 2 = 5 あまり 0 → 割り切れる
10 ÷ 3 = 3 あまり 1 → 割り切れない
10 ÷ 4 = 2 あまり 2 → 割り切れない
10 ÷ 5 = 2 あまり 0 → 割り切れる
10 ÷ 6 = 1 あまり 4 → 割り切れない
10 ÷ 7 = 1 あまり 3 → 割り切れない
10 ÷ 8 = 1 あまり 2 → 割り切れない
10 ÷ 9 = 1 あまり → 割り切れない 10 ÷ 10 = 1 あまり 0 → 割り切れる

1,2,5,10で割り切れたため、約数はこの4つです。
ただし、10が素数であるか判定する場合には、1以外で割り切れる整数が見つかった時点で探索を終了出来ます。
10であれば2で割り切れることが分かれば、5で割り切れることも明らかです。
実際には、その数の平方根まで探せば十分です。

#!/usr/bin/awk -f

function is_prime(n,    i){
    if(n <= 1){
        return 0;
    }else{
        for(i = 2; i <= sqrt(n); i++){
            if(n % i == 0){
                return 0;
            }
        }
        return 1;
    }
}

BEGIN{
    for(i = 0; i <= 199; i++){
        if(is_prime(i)){
            printf "%d ",i;
        }
    }
}

awk -f is_prime1.awk 
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

素数を求める方法として「エラトステネスのふるい」があります。
これは、指定された範囲の中から2で割り切れる数、3で割り切れる数、・・・と割り切れる数を順に除外する方法です。

#!/usr/bin/awk -f


BEGIN{
    n = ARGV[1];
    for(i = 2; i <= n; i++){
        data[i] = i;
        for(j = 2; j <= n; j++){
            if(data[i] % j == 0 && data[i] != j){
                data[i] = 0;
            }

        }
    }
    for(k = 2; k <= n; k++){
        if(data[k]){
            printf "%d ",data[k];
        }
    }
}

awk -f eratosthenes.awk 200
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