リセットせざるを得ない 素数マスターへの道を書き始めたころ、『とにかく1位をめざそう！！』という気持ちが動機の8割くらいだったので、文章の内容の構造をあまり考慮せずに進めてしまいました。このまま進めても良いかもしれませんが、なんとなく途中で話…

お嬢さん、お名前は？ 除算って遅いんです。 多少なりともプログラミングをやったことのある人にとっては「何を今さら」という内容ですが、あまりプログラミングを知らない方も読んでくださっているようなのでご容赦を。 で、どのくらい遅いのかということを…

解いてみよう これは中学生向けの問題です。正しく解答することができますか？ (問1)連続する3つの自然数がある。 一番小さい数とまん中の数の2倍の和が、一番大きい数の2倍と等しい時、 3つの自然数を求めなさい。ただし解き方も書きなさい。

ちょい脱線 前回、 水さすようで申し訳ないんですが、フェルマーテストはカーマイケル数に対して高確率で false positiveになります。 ミラー・ラビン素数判定は一つの底で判定する度に1/4の確率でしか素数性を担保出来ません。 確実な素数判定となるとAKS素…

試し割の効果 最初に書いたプログラムは、あまり速くはありませんでした。理由は、大きな素数が現れた場合に4千回以上も試し割りをしなければならないからです。プログラムを実行した結果、判定する33,333,333個の整数の中に、素数は3,260,532個でありました…

すげーぜ！ミラー・ラビン フェルマーテストによって、高確率で素数判定が出来るようになりましたが、もうちょっと確率の高い判定法があります。

フェルマーテストの実装 まずは、基数を色々変えられる一般的なものを書いてみます。

フェルマーの小定理 フェルマーの小定理という、素数判定には欠かせない定理があります。 3,5,7,11という素数を使って、以下のような計算をしてみます。 2^ 3 = 8, 8 / 3 = 2 余り2 2^ 5 = 32, 32 / 5 = 6 余り2 2^ 7 = 128, 128 / 7 = 18 余り2 2^11 =2048,…

はじめに 素数の問題は小学生くらいの知識であっても取り組むことが出来る。しかし奥深さは世界の天才数学者をも悩ませる。 ドイツが生んだ大数学者ガウスは言った。「素数は数学のょぅι゛ょであるﾊｧﾊｧ」うそ。言ってない。それはさておき、コンピュータと素…

せっかくなので 受験生から「解説よろノ」と言われたので作ったのだけど，せっかくなのでここに書いておきます．まあ，需要はあんまりないだろうけど．間違いとかあったらスマソ．

すんばらしい本を見つけました。 これはProject Eulerで遊ぶ人のために書かれたんじゃないかというくらい、どんぴしゃな内容です。数論の入門的な本は、今までいくらか読んでみたのですが、比較にならないくらい読みやすい。文章が柔らかいだけじゃなくて、…

遅れ馳せながら、Project Eulerに参加しました。去年funnythingさんがハマりまくっているのを見て、「これは危険だ」と手を出さないようにしていましたが、ついにやっちまいました。…面白いっす(>_結局1日10問くらいのペースで1週間続けてしまいました。多分…

行列を使うとフィボナッチ数は で計算できるので、前もってn=1,2,4,8,..2^kについて行列を計算しておけば、結構な速度で求められるようだ。まあ、Cだとオーバーフローを気にせなイカンのであまり使えなさそうだが(;´д｀) int p[30][4]={{1,1,1,0}}; mul(int*…