『エラトステネスの篩』の記述例（シェルスクリプト版）

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

記述例

※言語仕様に配列がないため，数字連番の変数を配列代わりとしています．

sieve.sh

read x
A1=1
c=0

i=1
while [ $i -le $x ]
do
  R=$((A$i + 0))
  case $R in (0)
    j=$((i*i))
    while [ $j -le $x ]
    do
      : $((A$j = 1))
      j=$((j+i))
    done
    c=$((c+1))
    r=$i
  esac
  i=$((i+1))
done

echo $c
echo $r

実行例

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

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

$ time dash sieve.sh <<< 10000
1229
9973

real    0m0.357s
user    0m0.330s
sys     0m0.010s

備考

更新履歴

• 2022-01-12：アルゴリズムおよび実行例（一万までの素数）の変更
• 2022-01-02：元記事より分離（コメントよりコード反映）