『エラトステネスの篩』の記述例（awk版）

元記事より分離しました．趣旨は元記事と同じく『「エラトステネスの篩」だとこれだけ速く素数が求まる！』ですが，仕様・処理系に大きな制約のあるプログラミング言語については，他の言語との比較を避けるため，個別記事としている次第です．

記述例

sieve.awk

BEGIN {
  getline x
  a[1] = 1
  c = 0

  for (i = 1; i <= x; i++)
    if (!a[i]) {
      for (j = i * i; j <= x; j += i) a[j] = 1
      r[c] = i
      c++
    }

  print c
  print r[c-1]
}

実行例

次の実行環境にて，百万までの素数の個数と最大の素数を表示しています．

• ASUS Zenfone 5: Qualcomm Snapdragon 636 1.8GHz, 6GBメモリ
• Android 9 + Termux + AnLinux(Debian GNU/Linux 10) + mawk1.3.3

$ time awk -f sieve.awk <<< 1000000
78498
999983

real    0m5.335s
user    0m5.080s
sys     0m0.120s

備考

更新履歴

• 2022-01-12：アルゴリズムおよび実行例（百万までの素数）の変更
• 2022-01-02：素数一覧を求めてなかった箇所を修正
• 2022-01-02：元記事より分離