屋根裏

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサー広告 |

素数判定

別のところで色々な自然数について、素数かどうかを判定していたが、それには適当な素数で割っていくしか方法はないのだろうか?

どうやら、最近の大きな数字についての判定はランダムな試行を繰り返して、ある程度の回数「素数ではない」と言われなかったものについて素数だとする確率的素数判定法なるものがあるらしい。
この試行のアルゴリズムがどうなっているのかも気になるところだけれど、今回はもっと簡単に、素数というのがどんな性質を持つのかという点に焦点を絞った。

早速少し調べてみた(考えろよ。
いや、考えたけれどもさ。
ちょっと思い浮かばなくてさ・・ごめんよ・・

おほん。
えぇ気を取り直して。
特に気になった、かっこいい定理を一つ挙げておく。

定理。
2 以上の自然数が総ての項が自然数からなる公差 2 の等差数列の連続する和で表される為の必要且つ十分条件は, その数が素数でないことである。

というのがあるらしい。
これの証明は明日くらいに考えるとして、また素数を抱きたくなったときのための備忘録として。


素数なら、適当な公差2の等差数列の和では表すことができないということ。
スポンサーサイト

computing | コメント:2 | トラックバック:0 |
<<宇宙いずくんぞ歌うべからざるや | HOME | 丑と牛>>

この記事のコメント

まったくね。
そんな表現が見つかれば、素数はもっと身近になる。

和のほうが積よりも簡単に計算できそうな気もする(項数が未知だから実はそうでもないけれど。

あと、ある数が素数かどうか判定するのは、多項式時間できるらしい。素晴らしい。
2009-01-04 Sun 20:15 | URL | adbmal #-[ 編集]
「表す事ができる」だったら話は早かったのにね。
2009-01-04 Sun 17:08 | URL | tief #-[ 編集]

コメントの投稿















コメント非公開の場合はチェック

この記事のトラックバック

| HOME |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。