素数の時にEnrico Pucciと出力するプログラムを書いてみた

ドラクエ、素手プレイのため、

全然先に進めません。

みけです。

おやおや！

FizzBuzz問題が話題になっているさなかですが、

面白いエントリーがあったので、批判しつつ取り上げます。

SST

素数のときだけ"JOJO!"って出力するプログラムを作ってみた - くりにっき

まあ、Rubyを応用したシンプルなプログラムです。

ただ、Integer#prime?という言語に元々ある素数判定を使うのは

反則な気がしなくもないかな。

この問題のポイントは素数であるか判定できるプログラムを書くことなので…

KPT

素数のときにJoJo - scala - - 言葉をポッケに持ち歩こう

Scalaをつかった、これまたシンプルな実装です。

Scalaには素数を判定するというメソッドがないので、

自前で実装しています。

それはいいんだけど、計算量が多すぎるorz

例えば、素数1009を素数であると計算するための計算回数が、1007回になります。

そんなに計算する必要はありません。

計算量

どれくらい計算する必要があるかというと、

2で割り切れるかどうか調べたら、対象となる数値の約1/2まで、

調べれば良いことがわかると思います。

何故ならば、対象となる数値(N)の1/2より大きい数値(M)は、

もはや商が1で余りがM - Nなので、

Mの値を増やしていっても商が1以外の数値を取ることはないからです。

同様に、3で割り切れるかどうか調べたら、対象の数値(N)の1/3より大きい数値は

もう調べる必要がありません。

何故ならば、Nの1/3より大きい数値MでNを割ると、

商1または2、余り1～Mの間の値になるからです。

という感じで、割り算をする値kをインクリメントしつつ、

チェックする最大値MをN/kとして限定していくことで、

計算量を減らします。

屁理屈はここまでで…

素数の時にJOJOと出力するプログラムを書こうとしたのですが、

素数でJOJOと言ったら、忘れることのできないキャラが居ますね。

プッチ神父です。

というわけで、素数になったら、Enrico Pucciと出力されるプログラムを

JavaScriptで書きました。


サンプルではまあ、他のブログのご多分に漏れず、1～100までやっています。





JavaScript可愛いですね。