Ｑｕｉｃｋ ＢＡＳＩＣの練習（８）～素数の判別、エラトステネスのふるい

また１ヶ月、間が空いてしまったので、思い出すのに苦労してしまったが、初

心者用の無料ソフト「クイック・ベーシック」を使って、地道にプログラミングの

勉強を続けよう。

これまでの関連記事９本（２本＋７本）は以下の通り。ほぼ完全に知識ゼロ、

ソフトも無い初心者状態からスタート。必要なら過去記事に戻って読むことを

お勧めする。

　　初めてのプログラミング♪

　　　　　　　　　　　　　　～メモ帳でバッチファイル作成（コマンドプロンプト用）

　　初めてのプログラミング（２）～計算その他、簡単なバッチファイル

　　　　・・・・・・・・・・・・・・・・・・・・

　　Ｑｕｉｃｋ　ＢＡＳＩＣのダウンロード、ダイレクトモード（Ｉｍｍｅｄｉａｔｅ）入力と計算

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（２）～プログラム・モードでの入力＆実行

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（３）～ＲＥＭ 文、ＧＯＴＯ 文、ＩＦ 文、各種トラブル・・

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（４）～ＩＦ文、ＦＯＲ文、ＮＥＸＴ文とループ（繰返し）

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（５）～二重ループ、流れ図（フローチャート）

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（６）～ＤＩＭ文と配列変数（添字つき変数）

　　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（７）～関数値の計算、方程式の近似解

テキストはいつもの通り、一昔前の高校数学の教科書、数研出版『数学Ａ』

（１９９５年版）。教科書のままだと上手く行かないこともあるし、勉強にもなら

ないので、マイナーチェンジや試行錯誤を繰り返すことになる。次回で一通り

終了で、その後は『数学Ｂ』に進む予定。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

今回扱うのは旧・数Ａの教科書で最後のセクション、｢自然数の列への応用」。

その大部分は素数の判別、判定の話で、残りが数Ⅱの数列の先取りとなっ

てる。素数というのも、２、３、５・・・と続く数列と考えることが出来るわけだ。

素数とは、２以上の自然数で、１と自分自身以外の約数を持たないもののこ

と。「２以上の」というのは要するに「１を除く」という意味で、素因数分解の一

意性を保つための配慮だという話を『モノグラフ』か何かで読んだ。

例えば、６を素因数分解すると、２×３の１通りに定まる。ところが、もし１を素

数に入れてしまうと、１×２×３とか、１×１×２×３なども可能になってしまう。

「１は１回のみ」と決めてもいいはずだけど、それよりは「１は素数でない」とし

た方が美しいということか。あるいは、他にも理由があるのかも知れない。

実際問題として、ある数が素数かどうかという判別は、その√以下の素数で

割れるかどうかチェックすればよい。例えば２９なら、√２９を考えると５より少

し大きい数だから、２、３、５で割れるかどうかをチェック。すぐにダメだと分か

るから素数だと判別できる。私が自分で気付いたのは中１か中２の頃だった。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

コンピューターのプログラミングだと、色んな書き方があるだろうけど、まず

　は教科書・例２７

　を少し変えたもの

　を示そう。

　自然数Ｎを入力し

　た時、それが１な

　ら「素数でない」、

　２なら｢素数」と判

　別。それ以外の

　　Ｎに対しては、

　　２～Ｎ－１の自然

　　数で割り切れるか

どうかを調べて、どれかで割り切れたら｢素数でない」、どれでも割り切れなかっ

　　たら｢素数」と判別する。実行して

　　１から順に入力すると、左のよう

　　に正しく判別された。

　　今回、初めて使ったのが、整数を

　　整数で割り算した時の余りを示

　　す組み込み関数「ＭＯＤ」。例え

　　ば、「８　ＭＯＤ　３」なら、８÷３の

　　余りで、答は２となる。丸カッコで

　　（８　ＭＯＤ　３）とくくる必要はない。

「ＭＯＤ」は「ｍｏｄｕｌｏ」（法）の略。

試しに０で割ろうとしたら、「Ｄｉｖｉｓｉｏｎ　ｂｙ　ｚｅｒｏ」（０での割り算）というエラー

メッセージが登場。また暴走するのかと思ってたので、少し安心、少しガッカリ

した♪　ちなみに、割り算の商を計算する記号「￥」は、私の環境だとまだソフ

トに入力できない。外付けの日本語キーボードでもダメだった。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

　　続いて、自分でいちいち

　　自然数Ｎを入力しなくて

　　も、素数だけ並べて表示

　　してくれるプログラム。

　　「ＦＯＲ～ＮＥＸＴ」構文で

　　１から１００までのＮを入

　　力させる以外は、前のプロ

グラムと同様だ。元になってる教科書・問１３の場合、ヒントとして流れ図が

　　書いてあった。実行する

　　と左のようになる。ズラッ

　　と並んでしまうので、右側

はカットした。これを適当な横幅で整列させる操作は、下で行ってるが、かな

り面倒だ。

　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

最後に、わりと有名な「エラトステネスのふるい（篩）」について。古代ギリシャ

（紀元前３世紀頃）の学者が考案したとされてる方法で、名前が大げさで難し

そうだが、手作業だと小学生でもすぐ分かる簡単な素数発見法だ。

　　左のように自然数を書

　　き並べて、素数でない

　　ものを少しずつ消して

　　行く。つまり、ふるいに

　　かける。

　　まず、１はすぐ消して、

　　２はＯＫ。つまり、素数。

　　次に２の倍数（偶数）を

　　消した状態が左図。別に５

　　個ずつ並べる必要はない

　　ので念のため。ブログのス

ペースの横幅を考慮してるだけなのだ。

　　残った数の内、最初の３

　　はＯＫ（素数）で、３の倍

　　数（２倍、３倍・・・）を順に

　　消して行く。既にこの時

　　点でかなり数が減少。次

　　は５を素数として、その

　　２倍、３倍・・・を消す。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

このふるいにかける操作をプログラミングするのは、読み取るだけでも難しい。

数Ａの教科書に載ってるものの中では最難関で、まず教科書通りに入力して

実行するように指示されてた。私も最初はそのまま入力＆実行してみたけど、

ここでは少し変えたものを掲載しよう。

最大のポイントは、Ｐ（Ｎ）という配列変数を考えること。斜線やバツ印で消す

代わりに、素数以外の数には「１」という数をマーク（記号）として対応づける

（初期値はいつも自動的にゼロ）。例えば、「Ｐ（４）＝１」という式が、「４は素

数でない」ということを表してる。実行結果では、４という数字は表示せず、

代わりに「・・」となる。

１～５０の自然数Ｎに対して、Ｍ＝２～２５の倍数を順に消していく。つまり、

Ｐ（Ｎ）＝１という対応付けを行っていく。２５というのは、「√５０より少しだけ小

さい自然数」の代わりに、もっと簡単な数を選んだということ。５０以下の自然

数が相手だと、一番大きな５０でさえ、２５の２倍として消せるわけで、２６以上

の倍数を考える必要はない。もちろん２５とか使わず、素朴にＭ＝２～５０とし

てもいい。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆　　

　　私が苦労したのは、話の本質よりも

　　枝葉の部分であって、実行の結果

　　を適当な形で整列させるのが難し

　　かったのだ。教科書のままだと、確

　　かに５個ずつで改行されるけど、空

　　白スペースが大き過ぎて横に広がっ

　　てしまうし、私の環境だとすぐ下の行

まではみ出て、変な並び方になる。

そこで、「・・」のすぐ右には半角スペースを２個、素数のすぐ右には半角スヘー

スを１個だけ入れると、まずまずの整列状況となった。

５個ずつで改行する時に使ってる技は、配列変数の添字Ｎを５で割った余り、

「Ｎ　ＭＯＤ　５」。これが０なら、Ｎが５の倍数ということで、次の行に移ることに

なる。改行の記号は、単なる「ＰＲＩＮＴ」。何もプリントするものが指定されてな

い時には、改行となるらしい。

次回は、いよいよ旧・数Ａの最後。数列の漸化式を解くことにしよう。

それでは、今日はこの辺で。。☆彡

ｃｆ．　Ｑｕｉｃｋ　ＢＡＳＩＣの練習（９）～数列の二項間漸化式と固有値、一般項

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（計　３００３字）