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

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

記述例

sieve.bc

x = read()
a[1] = 1
c = 0

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

c
r[c-1]

実行例

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

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

$ time bc sieve.bc <<< 1000000
78498
999979

real    0m2.907s
user    0m2.860s
sys     0m0.000s

備考

更新履歴

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