Ruby
Bash
awk

AWKで素数列挙(エラトステネスのふるい・疑似素数による試し割り)

More than 1 year has passed since last update.

需要あるのかしら(´・ω・`) まずはエラトステネスのふるい。

BEGIN {

upper_bound = 100

for (i = 2; i <= upper_bound; i++) is_prime[i] = 1;

for (i = 2; i <= sqrt(upper_bound); i++) {
if (!is_prime[i]) continue;
for (j = i * 2; j <= upper_bound; j += i) is_prime[j] = 0;
}

for (i = 2; i <= upper_bound; i++) {
if (is_prime[i]) print(i);
}
}

実装は以上。実行結果は以下の通りになります。

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

次に試し割りですが、ここでは疑似素数、つまり「2と3と、3 より大きくて 2 でも 3 でも割り切れない全ての整数」により次々割っていく方法を採用しています。

BEGIN {

upper_bound = 100

for (i = 0; i <= upper_bound; i++) {
if (is_prime(i)) print(i);
}
}

function is_prime(x, prime, step) {
if (x < 2) return 0;
if (x == 2 || x == 3 || x == 5) return 1;
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0) return 0;

prime = 7
step = 4
while (prime <= sqrt(x)) {
if (x % prime == 0) return 0;
prime += step
step = 6 - step
}

return 1
}

これも実行結果は以下の通りになります。

$ awk -f prime.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


確認用のRubyコードをここに張り付けておきますね(´・ω・`)

$ ruby -e 'require "prime"; Prime.each(100){|x| puts x}'

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

ちなみに次のようにしても素数列挙は可能です(´・ω・`)

$ seq 1 100 | xargs factor | awk 'NF==2{print $2}'

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