中学生向けのプログラミング教室でのこと、
運営に協力してくださっている学生から下記の様な質問を受けた。
プログラミングを書けるようになるために何をすれば良いですか?
と
ということで彼らに、
指定した数字の範囲内(例えば、1〜100までとか)にある素数をすべて出力してみたら?
と返答しといた。
※エラトステネスの篩(ふるい)は使わないという条件を設けた。
素数というのは、ある自然数があって、
その自然数が1と自分自身の数でしか割り切れない数のことを指す。
とりあえず、教室にいる中学生らも含めて下記の様な質問をしてみた。
5は素数ですか?と
返答は素数ですと返ってくる。
次に5がなんで素数なんですか?
と質問してみた。
この質問に対して、中学生から、
5が素数なんて当たり前じゃないですか!
と返答があった。
プログラミングというのは、
コンピュータに明確に指示を出さなければ絶対に動くことはないものです。
そこで、
当たり前ではなく、考えた過程を全て説明して欲しいと告げた上で、
再度5がなんで素数なのか?を答えてもらった。
5が素数であるということがわかるためには、
5までにある素数のすべてで割ってみて割り切れないことが分かれば良い。
指定した自然数よりも少ない素数すべてで割り算を試してみるためには、
すでにわかった素数の配列を作成する必要がある。
他に、
最初の素数として、2はわかっているものとする
ということでコードを書き始めた。
これからのコードはブラウザで実行するのが面倒なので、
Node.jsの方でJavaScriptを実行することにする。
最初に自然数を指定して、
指定した数までの自然数を表示するコードを書いてみる。
//自然数の指定 var N = 50; //ループは3から始める。 for (var i = 3; i <=N; i++) { console.log(i); }
これで、50までの自然数全てを表示出来た。
但し、1と2は予め外しておく。
次に2という素数で割って、約数に2を含まない数を保存する配列を用意してみる。
つまりは2と2の倍数以外の自然数全てを格納する配列となる。
var N = 50; //条件に合う自然数を格納する配列 var primes = [2]; var hit; for (var i = 3; i <=N; i++) { hit = false; if (i % primes[0] === 0) { hit = true; } //2で割り切れない数の場合はhitの値がfalseになる。 if (hit === false) { primes.push(i); } } //結果を表示する for (i = 0; i < primes.length; i++) { console.log(primes[i]); }
あとはprimesに素数を入れる仕組みを考えるだけになった。
primes配列には素数を見つけ次第格納されていくので、
Nで指定した自然数全てでprimesに格納された素数で調べてみる。
ここで大事になるのは、
指定した自然数で一つでも素数で割り切れれば、
指定した自然数は素数でないということになる。
これを加味すると、
var N = 50; var primes = [2]; var hit; for (var i = 3; i <=N; i++) { hit = false; //素数が格納されている配列で全ての数字で割ることを試してみる for (var j = 0; j < primes.length; j++) { if (i % primes[j] === 0) { hit = true; //一回でも割り切れれば、指定の自然数が素数でないことがわかるので、ここで割り算を止める break; } } if (hit === false) { primes.push(i); } } for (i = 0; i < primes.length; i++) { console.log(primes[i]); }
これで出来た。
このコードを実行してみると、
$ node s.js 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
とりあえず、素数は取れたっぽい。
今回の話をしていて感じたんだけど、
こういうやり取りがプログラミング教育で期待される論理的思考になるのかな?
小学生の算数や中学生の数学、
簡単な問題でも言葉にしていく過程を追加していくと途端に深くなる。
この手の課題をもっと考えてみよう。