福野泰介の一日一創

義務教育学校の算数の先生の「大きな素数を考えよう」というおもしろそうな課題。
素数かどうか判定するアプリを自作されたとのことですが、もうちょっとおもしろくしたいとのご相談。

単純な計算が合ってるかどうかは電卓で確認できますが、電卓にも限界があります。そんなときこそコンピューターとプログラミングの出番！

どういう手順で素数かどうか判定したらいいかを考え、実際にプログラミングして確かめると理解が深まります。

前提：素数とは、その数より小さく、2以上の数で割り切れない数。
思いつきの判定手順
1. 2で割ってみる。割り切れたら素数じゃない。
2. 3で割ってみる。割り切れたら素数じゃない。
...（以後、その数-1まで繰り返し）

で、判定できそう！と思いついたとしたら、実際プログラミングしてます。

10 INPUT A 20 B=2 30 IF A%B=0 ?"NOT SOSU...";B:END 40 B=B+1 50 IF B=A ?"SOSU!":END 60 GOTO 30

できたら、試してみましょう（RUN on IchigoJam web - ブラウザでも動かせます！）

RUN ?20 NOT SOSU...";2 OK RUN ?17 SOSU! OK

1777は素数でしょうか？実は、この考え方だと結構答が出るまでに時間がかかります。
考えてみると、その数-1まで律儀にみなくても素数かどうかの判定はできるかも！？
思いついたら即プログラミング！合ってるかどうかもまた自分で分かります。

この「考え方」が「アルゴリズム」と呼ばれる、プログラミングの真髄です！

この判定プログラムは、IchigoJamの限界、32767を超えてしまうと使えません。
そんな時、大きな数を扱う新たなアルゴリズムをつくりましょう。

答を書いてしまってもつまらないので、ここでは筆算を用いた大きな数の掛け算までを例示します。

(RUN on IchigoJam web) ブラウザ上で動きます！

とりあえず、画面に数式を表示します

10 CLS 20 LC8,0:?" 123456" 30 LC8,1:?"x 7" 40 LC8,2:?"--------"

6x7、5x7、、、と順に掛け算していきますね。まずは値を画面から取得してみます。

50 B=SCR(15,1)-48 60 A=SCR(15,0)-48 RUN ?A,B 6 7

48とはASC("0")、0を表すキャラクターコードなので、引くとその場所の数が分かります。

計算して1桁かいてみます

70 C=A*B 80 LC15,3:?C%10

あまりを求めるIchigoJam BASICの演算子「%」を使って、1桁計算できました。

繰り上がりを変数Dにいれつつ、変数Iを使った繰り返しで、大きな数 x 1桁の数 の筆算ができます。

55 I=15:D=0 65 IF A<0 GOTO110 80 LCI,3:?C%10 90 D=C/10 95 I=I-1 100 GOTO 60 110 IF D LCI,3:?D

20行、30行の問題をいろいろ変えて試してみましょう。

つづいて、複数桁 x 複数桁に対応してみます。例えば139で掛けてみます。

20 LC8,0:?" 123456" 30 LC8,1:?"x 139"

一桁ずつの計算を1つずつずらして表示します。

45 J=15 50 B=SCR(J,1)-48 52 IF B<0 END 80 LCI+J-15,3+15-J:?C%10 110 IF D LCI+J-15,3+15-J:?D 120 J=J-1 130 GOTO 50

最後に、縦の列を足し算すれば完成です！

52 IF B<0 GOTO140 140 LC8,3+15-J:?"--------" 150 I=15:C=0:L=3+15-J+1 160 J=3 170 A=SCR(I,J)-48:IF A<0 A=0 180 C=C+A 190 J=J+1:IF J<L-1 GOTO170 200 IF C=0 END 210 LCI,L:?C%10:C=C/10 220 I=I-1:GOTO160

じっくり時間を掛けて、自分のものにしてください。

大きな素数を判定するアルゴリズムづくり、挑戦してみよう！