数値が素数かどうかを判定するBashプログラムの書き方

Bash(GNU bash)は、Unix系オペレーティングシステムで広く利用されているコマンド言語兼シェルスクリプトのコマンドラインインタプリタです。Brian Foxによって設計され、従来のBourneシェル(sh)を置き換えるフリーソフトウェアとして1989年に初めてリリースされました。現在では、LinuxやmacOSなど多くのOSで標準のログインシェルとして採用されています。

素数とは、1とその数自身という2つの約数しか持たない正の整数のことです。例えば、2、3、5、7、11、13、17、19、23、29などが該当します。

この記事では、与えられた数値が素数であるかどうかを判定するBashスクリプトの作成方法を解説します。

問題の定義

入力 : 1つの整数
出力 : 判定結果に応じて「その数は素数です」または「その数は素数ではありません」

例 :

入力 : 23
出力 : その数は素数です

アルゴリズム

• ステップ1 − ループ変数 i を使い、2 から n/2 まで繰り返す。

• ステップ2 − number が i で割り切れた場合は「その数は素数ではありません」と表示し、flag を 1 に設定する。

• ステップ3 − flag が 1 以外の場合は「その数は素数です」と表示する。

• ステップ4 − 終了する。

Bashプログラム

number=53
i=2
flag=0
while test $i -le `expr $number / 2`
do
  if test `expr $number % $i` -eq 0
  then
    flag=1
  fi
  i=`expr $i + 1`
done
if test $flag -eq 1
then
  echo "The number is Not Prime"
else
  echo "The number is Prime"
fi

実行結果

The number is Prime

プログラムの仕組み

このスクリプトでは、変数 number に判定対象の数値(53)を代入しています。変数 i は 2 から始まり、number / 2 に達するまで1ずつ増加していきます。各ループ内で expr $number % $i により剰余を計算し、剰余が 0(割り切れた場合)であれば flag を 1 に設定します。

ループ終了後、flag の値を確認します。flag が 1 であれば途中で割り切れたことになるため素数ではなく、flag が 0 のままなら 1 とその数自身以外に約数が存在しない、つまり素数であると判定できます。

なお、この方法は n/2 まで調べるアプローチですが、実際には √n まで確認すれば十分です。大きな数値を扱う場合は判定範囲を sqrt(n) まで狭めることで、処理効率を大幅に向上させることができます。