Ruby
Bash
awk

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

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

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