−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
応用数学I・II 1995.5.16
6.配列を使って素数について調べる 飯島
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
6−0.はじめに
まだ,プログラミングを始めたばかりとはいえ,みなさんなりに,コンピュータを使っ
て数学を実験する感覚は掴めてきたと思いますし,たとえば整数について調べる程度のこ
とならば,十分にできると思うので,力を付ける意味もこめて,
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
来週(5/30)に第一回目の実技試験を実施!
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
したいと思います。知識を調べるのではなく,
コンピュータを使って実験ができるかどうか
を調べるわけですから,「持ち込み可能」であり,また「今までのプログラムも利用可能
」(使えるかどうかは別にして)使って構いません。ただし,友人との相談はしてはいけ
ません。(試験だからね。)
試験ではありますが,あまり神経質にはならないでください。みなさんの評価でもある
と同時に,授業の評価でもあるわけで,今後の進め方の資料にもしていきます。
さて,それで今日は,...
6−1.素数をまとめて作っておこう。
今日の材料は,「素数」です。次の項を見ると分かりますが,
素数+素数
なんかを調べたいのですが,前のように,
一つの数が素数かどうか
を毎回一つずつ調べているのでは「埒が明きません」。
そこで,
○番目の素数は○
というのを,一括して,事前に調べ上げておきたいと思うのです。
それを表すために,次のような表現があります。
prime(1)
prime(2)
....
要するに,カッコの中の番号が「何番目」というのを指しているわけですね。
こういうのを,「配列」と言います。
6−2.配列を使うためにはどうするか
さて,配列は,なにもしなくても使えるわけではありません。最初に「宣言」をしない
といせません。特に,「最大何番目まで」ということが必要です。
たとえば,10000以下の素数は,約1300個あるので,たとえば,次のようなプ
ログラムになります。
CLS
DIM prime(1300)
prime(1) = 2 (*)
prime(2) = 3 (*)
ct = 2 (*)
FOR n = 1 TO 10000
FOR i = 2 TO SQR(n)
check = -1
IF n MOD i = 0 THEN
check = 0
EXIT FOR
END IF
NEXT
IF check = -1 THEN
ct = ct + 1
prime(ct) = n
PRINT ct; ":"; n; "/";
END IF
NEXT
ここで,下線部に注意してください。
(1) prime という配列変数を,最大1300まで使えるように宣言しています。
(2) check が-1ということは,「素数」なので,その番号を1増やしました。
(3) そして,ct番目の素数はn だということを記録しています。
注−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
実は,最初は(*) の部分はなかったのですが,授業中,ある学生が「結果がおかしい
」ことを指摘してくれました。その結果,このアルゴリズムは修正する必要があり,
アルゴリズムを変えるよりは,この3行を追加する方が簡単で分かりやすいと思い,
そうしました。
さて,どうして,この3 行が必要なのか,余裕があったら考えてみてください。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
さて,このようにすると,一度つくっておけば,後で簡単に利用できるわけですが,た
とえば,計算し終わった後で,その結果を一通り表示させようと思うと,
CLS
DIM prime(1300)
prime(1) = 2
prime(2) = 3
ct = 2
FOR n = 1 TO 10000
FOR i = 2 TO SQR(n)
check = -1
IF n MOD i = 0 THEN
check = 0
EXIT FOR
END IF
NEXT
IF check = -1 THEN
ct = ct + 1
prime(ct) = n
PRINT ct; ":"; n; "/";
END IF
NEXT
FOR i = 1 TO ct
PRINT prime(i);
NEXT
と3行を追加すればいいわけです。なお,ctには,最後の素数の番号が記憶されているの
で,i は1 からctまでとなっています。
6−3.OKが出るのは,どんな数字?
上記のプログラムを修正して,次のものを作り,そして,いろいろな整数(10000
以下)を入力してみましょう。OKが出たり出なかったりしますが,どういう数に対して
,OKが出るのでしょう。自分の予想として,まとめてみてください。
CLS
DIM prime(1300)
prime(1) = 2
prime(2) = 3
ct = 2
FOR n = 1 TO 10000
FOR i = 2 TO SQR(n)
check = -1
IF n MOD i = 0 THEN
check = 0
EXIT FOR
END IF
NEXT
IF check = -1 THEN
ct = ct + 1
prime(ct) = n
PRINT ct; ":"; n; "/";
END IF
NEXT
FOR i = 1 TO ct
PRINT prime(i);
NEXT
DO
INPUT "input some integer<10000, 0->end"; n
IF n = 0 THEN END
FOR i = 1 TO ct
IF prime(i) > n THEN EXIT FOR
FOR j = i TO ct
IF prime(i) + prime(j) > n THEN EXIT FOR
IF prime(i) + prime(j) = n THEN
PRINT "OK!", prime(i); " + "; prime(j); " = "; n
EXIT FOR
END IF
NEXT
NEXT
LOOP
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
|OK |
| |
| |
| |
| |
| |
| |
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
|OKでない |
| |
| |
| |
| |
| |
| |
+−−−−−−−−−−−−− 予 想 −−−−−−−−−−−−−+
| |
| |
| |
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
6−4.三つの素数の和にしたらどうなる
上記は,二つの素数の和でしたね。さて,では,これらを三つの素数の和にしたら,一
体どういう結果(予想)が得られるのでしょう。
プログラムを修正し,次に結果の表を作り,そして予想してみましょう。
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
|OK |
| |
| |
| |
| |
| |
| |
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
|OKでない |
| |
| |
| |
| |
| |
| |
+−−−−−−−−−−−−− 予 想 −−−−−−−−−−−−−+
| |
| |
| |
+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+
なお,これらの証明に挑むのは自由ですが,没頭しすぎるのはいけません。
関心がある人は,「ゴードバッハの予想」というのを,数学辞典などで調べてみてくださ
い。
6−5.配列では,こんなこともできる(1) 最大値・最小値・平均
配列を使うと,こういうことも簡単です。
CLS
DIM x(10)
PRINT "input ten numbers"
FOR i = 1 to 10
input x(i)
NEXT
PRINT "Your Numbers : ";
FOR i = 1 to 10
PRINT x(i);
NEXT
PRINT
MAX=-100
FOR i = 1 to 10
IF x(i) > MAX THEN MAX = x(i)
NEXT
PRINT "Max : "; MAX
では,「最小値」も表示してみましょうね。
・・・・
それから,「平均」も簡単です。だって,
平均=総和/個数
ですから,
CLS
DIM x(10)
PRINT "input ten numbers"
FOR i = 1 to 10
input x(i)
NEXT
PRINT "Your Numbers : ";
FOR i = 1 to 10
PRINT x(i);
NEXT
PRINT
Sum = 0
FOR i = 1 to 10
Sum = Sum + x(i)
NEXT
PRINT "Mean : "; Sum / 10
でOKです。
こういうのをすべて x1, x2, ...としなければならないとすると,... 大変ですね。
6−6.配列では,こんなこともできる(2) 並び換え
それから,こういうこともできます。
CLS
DIM x(10)
PRINT "input ten numbers"
FOR i = 1 to 10
input x(i)
NEXT
PRINT "Your Numbers : ";
FOR i = 1 to 10
PRINT x(i);
NEXT
PRINT
FOR i = 1 to 10
FOR j = 1 to 10
IF i > j AND x(i) < x(j) THEN SWAP x(i), x(j)
NEXT
NEXT
FOR i = 1 to 10
PRINT x(i);
NEXT
PRINT
また,こういうことに関する詳しいことは,必要になったときにしますが,いずれにして
も,「配列」を使うと便利なことが多いのは事実です。
<以上>