プログラムの学習とアルゴリズム

この記事は2017年08月03日に公開されました。 情報が古い可能性があります。

こんにちは、殿内(@tonoccho)です

教えてござ先輩 のなかで、素数を判定するアルゴリズムが乗ってて、色々な意見の出る書き方をしていました。

プログラミングの考えとしては間違いではない

と思っています。というのも、きちんと素数が判定されるので。ただ、まぁ、このアルゴリズはナイワーというものであることも確かです。なぜなら、とにかくおそいからです。
とはいえ、これからプログラムを学ぶ人にとっては「2から順繰りに割っていき、割れる数字があった時点で素数ではないと判定する」は丁度良いところだと思います。

ここから進むかどうか

数学的にきちんと素数がわかっている人なら試行回数を削れるまで削っていき、これ以上は減らないところまで持っていけるかと思うんですけど、そうでない人、例えば高校生くらいの人や、数学の分野を学んできていない人はどうやって計算量を減らせばいいのか、というのもプログラミングの楽しみだと思います。
そんな彼らの結果は、数学的に最小ではないかもしれませんが、そうやって楽しめるか、と言うのも一つの大事な素養だと思います。

高校の時に同じ問題をやった

高校でプログラミングを勉強してて、どこかの大学の推薦問題に同じものがあり、最初はござ先輩の記事と同じ考え方でやったのですが、その時一人の友人が「これってもっと早く出来ないのかな」と言ったところからみんなで色々なアイデアを出しました。以下はその時のアイデアです。

この他にも、N以下の数字で、これらの数字で割り切れないならそれは素数ということを調べてきた友人もいました。

最終的に速攻終わるようになった

当初のプログラムと比べたら、え、そんなすぐ終わるの?と言うくらいに早くなりました。
そんな訳で、プログラミングをやる人は、一旦書いたもので満足せずに、どうすればもっと早いかな、とか、分かりやすいかな、と考える癖をつけるといいと思いますし、そう言った仲間を探して行くのもいいと思います。

ニュージーランドの最新記事

生活の最新記事