素数を計算するシェルスクリプト

バンコクの id:KoshianX 氏の食客となってはや10日以上が過ぎた。手練のハッカーである彼とは、ついつい話が技術的な方向に向かっていく。先日、紹介してくれたのが

UNIXという考え方―その設計思想と哲学

という本。UNIX の特徴を9個の定理として表現している。基本的な考え方は「小さなツールをたくさん作り、それを組み合わせることで、90％の問題を解決しましょう」ということ。力の入らない実用本位の考え方だ。UNIX を使っていると自然に身に着いてしまうんだけどね。

読み終わったあと、なんだかむしょうにシェルスクリプトのプログラムが書きたくなった。

• 定理5「数値データは ASCII フラットファイルに保存する」
• 定理7「シェルスクリプトを使うことで梃子の効果と移植性を高める」
• 定理10「すべてのプログラムをフィルタにする」

にしたがって、「標準入力からパラメータ n を受け取り、n 以下の素数を全て求めて標準出力に吐き出す」というフィルタを bash で作ってみた。別にどってことはないんだけどね。とりあえず作ったので、さらしてみる。bash は元祖 B シェルに比べるとかなり拡張が施されていて格段にプログラミングしやすくなっている。Perl やら Ruby のある時代に、B シェルで本格的なプログラミングもないだろうけど、かなり複雑なことができそうな予感。遅いけどね。BASH Programming - Introduction HOW-TO(日本語版)を参考にするといいかも。

#!/bin/bash

function isprime() {
  local n=$1
  if [ $n -le 0 ]; then
    return 0
  fi

  if [ $n -le 2 ]; then
    return 1
  fi

  if [ $(($n % 2)) -eq 0 ]; then
    return 0
  fi

  local i=3
  while [ $(($i * $i)) -le $n ]; do
    if [ $(($n % $i)) -eq 0 ]; then
      return 0
    fi
    let i=i+2
  done
  return 1
}

read max

i=1
while [ $i -le $max ]; do
  isprime $i
  if [ $? -eq 1 ]; then
     echo $i
  fi
  let i=i+1
done

・・・と喜んで id:KoshianX 氏に見せたところ「bash を使うなんて軟弱だ！！！」と怒られたので（しくしく） Bシェル互換で書き直してみた。それが以下のコード。実行すると expr のせいでむちゃくちゃ遅い。

#!/bin/sh

#This should be Bourne shell compatible.

isprime() {
  n=$1
  if [ $n -le 0 ]; then
    return 0
  fi

  if [ $n -le 2 ]; then
    return 1
  fi

  if [ `expr $n '%' 2` -eq 0 ]; then
    return 0
  fi

  i=3
  while [ `expr $i '*' $i` -le $n ]; do
    if [ `expr $n '%' $i` -eq 0 ]; then
      return 0
    fi
    i=`expr $i '+' 2`
  done
  return 1
}

read max

j=1
while [ $j -le $max ]; do
  isprime $j
  if [ $? -eq 1 ]; then
     echo $j
  fi
  j=`expr $j '+' 1`
done