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

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

記述例

sieve.bash

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

i=1
while [ $i -le $x ]
do
  case ${a[$i]} in ("")
    j=$((i*i))
    while [ $j -le $x ]
    do
      a[$j]=0
      j=$((j+i))
    done
    c=$((c+1))
    r+=($i)
  ;;esac
  i=$((i+1))
done

echo $c
echo ${r[$c-1]}

実行例

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

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

$ time bash sieve.bash <<< 100000
9592
99991

real    0m4.717s
user    0m4.630s
sys     0m0.020s

備考

更新履歴

• 2022-01-12：アルゴリズムおよび実行例（十万までの素数）の変更
• 2022-01-02：元記事より分離