- 注意：これは、Pascal語によるプログラムの基礎講座です。
素数で遊ぼう！ Visitor No. - : - : -
- 素数の定義は飛ばして、私の以前勤めていた職場の電話番号はそのまま書くと問題なので.....1桁の2乗×２桁の2乗×3桁×3桁って実にうまく素因数分解できる番号でした。プリントゴッコの名刺で裏には地図と「電話番号を素因数分解すると」と前述の式を書き加えていました。裏を見るなりその場で電卓で計算をした人、2名いました。このときは、カシオのポケコン学校用VX-3でBASICでした。
- そんなわけで、ここでは、素数の求め方から、電話番号を素因数分解できる！までを作って見ましょう。
素数を求める
- 初級のプログラム講座の本には割と掲載されていたものです。
- こんなのがありますが、まず１に×、２に○をつけたら平行線で２の倍数をけす。次に３に○、平行線で３の倍数を消す.....と繰り返して素数を求める方法で、倍数を排除する方法です。
- 新しいFromを用意して、Button4個、出力用にmemo2個、Edit1個を用意しましょう。
- MemoのScrollBarsは、ssVerticalにしておきましょう。
- Button2は、captionをEndでもExitでも終わりでも好きなようにして、以下の様にしましょう。
- それから、Form1のイベントのonCreateで、Memo、Editの文字をなくしましょう。なぜプログラム中で消すかと言うと、プログラムを記述しているうちは、表示されているほうがやり易いので、起動で消すようにしています。
- とりあえず、これで何もしないけど終了ボタンを備えたwindows用プログラムの完成です。ここまでは、説明するまでもないないことでしょう。
- 何度も使うファイル名を以下のように先頭で定義しておきましょう。{$R *.DFM}--ここは元々ある行です。その下に定数文字列として設定します。
- Button1の初期設定をしましょう。
- まずは、求める素数の最大値を決めておきましょう。
- それから、上の図で使っているカレンダーに匹敵する入れ物を用意しなければなりません。入れ物名「suuji」で1から100まで用意しました。中に入るのは、真偽ですが、integerで用意して、0な偽、1なら真としてもかまいませんけど.....
- 1から100まで調べるので整数の変数iを用意。nは、素数の倍数を扱う変数です。
- 1から100まで、全員が「私は素数です」と表明している状態にします。{中身をリセット}
- とりあえず100以下の素数が求められました。今のパソコンでは、時間を計るのか、プログラムに組み込まないとできません。しかし、私が最初に買ったCASIO FP-1100の8bit 4MHzのものでは10秒近くかかったのです。
- ところで、100までの素数が求められれば、これを使って効率よく、100の２乗までの素数が求められます。この辺は、中学の頃の数学「約数を全て求めよ」です。任意の自然数ｎの約数を求めるのに、１から√ｎまでの整数を調べればいいわけですから.....
- そんな訳で、日本の電話番号は11桁ありますが、11桁になるとint64の登場になるんですが、sqrt関数で扱えず、とりあえず10桁電話番号でやることにして、ただし、11桁たいおうの準備はしておきましょう。最初は0ですし、仮に逆並び数字にしても最後が0で、必ず、2と5で割り切れることになりますから、最大の数は、10,000,000,000-1です。したがって用意する素数は10,000,000,000の平方根になる100,000までの素数を準備すれば、電話番号の素因数分解ができることになります。100,000までの素数を調べるには、316までの素数を準備すればOKなんですが、とりあえずパソコンのCPU力まかせでmax=1000にしちゃいましょう。
10万までの素数を求めよう。
- Memoの限界行数を越えないことを願いつつ..........だめだったら、HDD上に直接ファイルを開きましょう。
- 準備としてButton3と4、Memo2、Edit1を追加しましょう。Memo2は、Memo1と同じ設定にして、最終的に電話番号の素因数分解結果を出力するので、ちょっと横を広く取っておきましょう。
- そしたら、Memo1.Lines.SaveToFile('素数.txt');もMemo1.Lines.SaveToFile(f_name1);としておきましょう。
- で、Button3の中身が以下のようになります。BASICのラベルジャンプの癖が抜けません。
- beginの次の行ですが、結果がtrueの場合は「=true」をつける必要がありません。
- Memo2にも「素数.txt」を読み込んでいます。これは、1001からの結果と連結するためです。
- repeatの次の行にある「mod」は、あまりを求める関数です。10 mod 3 = 1 とか 10 mod 4 = 2 です。結果が0だったら、次のiで検証するわけです。
- 早速コンパイル、Button3をクリック.........やってる、やってる...数字が書き込まれていくのが見えます。Memo2を非表示にするともっと早いんですが、面白くありません。この発想は、数毒を解くプログラムも、平方根を100桁求めるプログラムも一緒です。意味もなく作業を表示させたりしたほうが。面白い。
- 約9600個の素数がありました! これを、「素数.dll」(direct link library)で保存します。素因数分解で使いますから....
準備完了で、電話番号を素因数分解
- ためしに、救援連絡センターの番号を素因数分解してみました。結果は自動的に保存されます。
ところで.....(2009/11/19)
- 最近TVで素数の話をやっていた。150桁以上の巨大素数が暗号通信に使われることは知っていたが、その理由は、巨大桁数計算機が存在しないことに素数を使う意義があるんだそうだ。
- 仮に巨大桁数の計算機を作るとしよう。500桁くらいは出したい。巨大なそろばんを想定し、2桁で1byte、高速なのは、アセンブリで書くこととなるけど.....普通に配列で処理するとして
- 下1桁が、偶数排除、５排除、各桁数字の和が3で割れれば排除、残りについて7から順に割っていって調べることになる。当然時間がかかるので、途中の保存機能をつける。
- さて、計算機は平方根を求められること。12345678x10^41なら、√(1234568)x√(10^42)として、多少の無駄はでるが、概数で出せる。
- 割り算は、掛け算と引き算の合成。掛け算は、文字列比較で桁調整すれば....不可能ではない。発見したら、順に保存して、そのファイルをそのまま参照しながらさらに次のものを求めていくことになる。
- ちょっとプログラミングの練習にやるのも楽しいかもしれない。
- その前にこのプログラムを改造して9桁までの素数を全て求めておくことも必要になるかな.....
最終更新：2009年11月19日 20:14
