■中学生でもできる！　素因数分解プログラムを書いてみよう（bashで）

http://anond.hatelabo.jp/20170117205622

より。

「ワイは全然すごくない」という増田の書き込みに対して「いや全然すごいよ」みたいな書き込みが散見されるようだが、ここではっきりと申し上げておきましょう。

「素因数分解をプログラムで解くとかとか中学生でもできるぞ」と。つまり、増田は全然すごくないし、この記事を書くワイも全然すごくない。

素因数分解というのはなんか用語だけ聞くと難しそうに思うが、要は「ある数字を素数の組み合わせに分解」するだけの話である。

数字を素数で割っていけば自然と素因数分解が行えるのである。

というわけで増田が全然凄くないの根拠として、以下に素因数分解を行うプログラムのサンプルを挙げる。

このプログラムはbashで書いてあるが特にbashである必然性はないのでphpなりCで書き直してみるといいだろう。

中学生のお子様がいるご家庭の方は、これをサンプルとして別の言語で書かせてみると、その子のプログラミング的素養が図れるかもしれない。

#! /bin/bash

n=$1;
a=2;
while [ $a -lt $n  ]
do
  #割って余りが0なら素因数やな！
  m=$((n%a));
  if [ $m == 0 ]
  then
    # $n は 素数やない！ $a で割り切れんで！
    #a自体が素数かどうか調べなあかんわ
    echo -n "${a}x";
    n=$((n/a));
    a=2;
    continue;
  fi
  #素因数やないので割る数を増やしてみるで
  a=$((a+1));
done;
#余った $n は素数やな
echo  $n;

（最初のソースはバグってた。ちょっと直しました）

このソースをtest.shなどのシェルスクリプトファイルを作成してその中に記述する。ソースを記述した後はchmod +x で実行権限をつけてあげることを忘れないようにしよう。

このプログラムは渡された一番目の引数に対して素因数分解を行う。整数以外を入れた場合の動作は保証できないので、適宜チェック処理を入れるなりしよう。

このプログラムを実行すると、結果は以下のようになる。

$ ./test.sh 114514
2x31x1847

結果が不安なら電卓で計算してみればいい。必ず合うはずだ。

ついでにクリップボードにコピーする

結果を出すのはいいとして、元増田はクリップボードにコピーして貼り付けまでを手動で行っていたそうな。

MacOSならばクリップボードにコピーするまでを一貫して行うことも可能だ。pbcopyというコマンドを使う。

$ ./test.sh 114514|pbcopy

これでクリップボードにコピーされた状態になるので、そのままニコニコなりのコメント欄にコピーすればいい。これで俊速素因数分解コメントが書き込めるようになる。

また、いちいちpbcopyコマンドを打つよりも今回作成したシェルスクリプトの中でpbcopyまでを行ってしまうのもありかもしれない。

いずれにせよ、今回の素因数分解というプログラムはかなり簡単な部類になるため、初心者への課題としてはうってつけだ。

どうです、簡単でしょう？　

ちなみに実行速度ですが、よほどデカイ素数でもない限りジョン・フォン・ノイマンの暗算よりは早いはずです。多分……

ツイートする

Permalink | トラックバック(2) | 06:08