« 腰痛と強風のハーフ走&青梅マラソン&春ドラマ | トップページ | 居住だけは別にした外国人受け入れ~曽野綾子「労働力不足と移民」(産経新聞) »

Quick BASICの練習(8)~素数の判別、エラトステネスのふるい

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

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

勉強を続けよう。

これまでの関連記事9本(2本+7本)は以下の通り。ほぼ完全に知識ゼロ、

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

お勧めする。

 

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

              ~メモ帳でバッチファイル作成(コマンドプロンプト用)

  初めてのプログラミング(2)~計算その他、簡単なバッチファイル

 

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

  Quick BASICのダウンロード、ダイレクトモード(Immediate)入力と計算

  Quick BASICの練習(2)~プログラム・モードでの入力&実行

  Quick BASICの練習(3)~REM 文、GOTO 文、IF 文、各種トラブル・・

  Quick BASICの練習(4)~IF文、FOR文、NEXT文とループ(繰返し)

  Quick BASICの練習(5)~二重ループ、流れ図(フローチャート)

  Quick BASICの練習(6)~DIM文と配列変数(添字つき変数)

  Quick BASICの練習(7)~関数値の計算、方程式の近似解

 

 

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

1995年版)。教科書のままだと上手く行かないこともあるし、勉強にもなら

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

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

 

 

           ☆          ☆          ☆

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

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

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

 

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

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

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

 

例えば、6を素因数分解すると、2×3の1通りに定まる。ところが、もし1を素

数に入れてしまうと、1×2×3とか、1×1×2×3なども可能になってしまう。

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

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

 

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

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

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

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

 

 

           ☆          ☆          ☆

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

150217a は教科書・例27

 を少し変えたもの

 を示そう。

 

 自然数Nを入力し

 た時、それが1な

 ら「素数でない」、

 2なら「素数」と判

 別。それ以外の

  Nに対しては、

  2~N-1の自然

  数で割り切れるか

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

150217b  たら「素数」と判別する。実行して

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

  に正しく判別された。

 

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

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

  す組み込み関数「MOD」。例え

  ば、「8 MOD 3」なら、8÷3の

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

  (8 MOD 3)とくくる必要はない。

「MOD」は「modulo」(法)の略。

 

試しに0で割ろうとしたら、「Division by zero」(0での割り算)というエラー

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

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

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

 

 

           ☆          ☆          ☆

150217c  続いて、自分でいちいち

  自然数Nを入力しなくて

  も、素数だけ並べて表示

  してくれるプログラム。

 

  「FOR~NEXT」構文で

  1から100までのNを入

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

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

150217d  書いてあった。実行する

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

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

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

り面倒だ。

 

 

          ☆          ☆          ☆

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

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

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

 

150217e  左のように自然数を書

  き並べて、素数でない

  ものを少しずつ消して

  行く。つまり、ふるいに

  かける。

 

  まず、1はすぐ消して、

  2はOK。つまり、素数。

  次に2の倍数(偶数)を

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

  個ずつ並べる必要はない

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

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

 

150217f  残った数の内、最初の3

  はOK(素数)で、3の倍

  数(2倍、3倍・・・)を順に

  消して行く。既にこの時

  点でかなり数が減少。次

  は5を素数として、その

  2倍、3倍・・・を消す。

 

 

 

 

 

           ☆          ☆          ☆

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

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

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

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

 

150217g

 

 

最大のポイントは、P(N)という配列変数を考えること。斜線やバツ印で消す

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

(初期値はいつも自動的にゼロ)。例えば、「P(4)=1」という式が、「4は素

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

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

 

1~50の自然数Nに対して、M=2~25の倍数を順に消していく。つまり、

P(N)=1という対応付けを行っていく。25というのは、「√50より少しだけ小

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

数が相手だと、一番大きな50でさえ、25の2倍として消せるわけで、26以上

の倍数を考える必要はない。もちろん25とか使わず、素朴にM=2~50とし

てもいい。

 

 

           ☆          ☆          ☆  

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

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

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

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

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

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

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

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

 

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

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

 

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

「N MOD 5」。これが0なら、Nが5の倍数ということで、次の行に移ることに

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

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

 

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

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

 

 

cf. Quick BASICの練習(9)~数列の二項間漸化式と固有値、一般項

 

                                     (計 3003字)

|

« 腰痛と強風のハーフ走&青梅マラソン&春ドラマ | トップページ | 居住だけは別にした外国人受け入れ~曽野綾子「労働力不足と移民」(産経新聞) »

数学」カテゴリの記事

プログラミング」カテゴリの記事

コメント

ちょっと見ない間にだいぶ進んでますね。

投稿: U | 2015年2月23日 (月) 19時45分

> 友人U
   
結局、高校の教科書1冊分に1年かかった (^^ゞ
おまけに全然、消化不良だから、
あんまし分かった気がしないよ♪

投稿: テンメイ | 2015年2月24日 (火) 01時50分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« 腰痛と強風のハーフ走&青梅マラソン&春ドラマ | トップページ | 居住だけは別にした外国人受け入れ~曽野綾子「労働力不足と移民」(産経新聞) »