ある整数を割り切れる素数を知るには？

例えば２６１３という整数を割り切れる素数を全て知る方法はありますか？

No.3 ベストアンサー 回答者： kabaokaba 回答日時： 2012/03/27 21:43

全部調べる．基本はこれしかない．

素因数分解は素数の約数（素因数）が分かって初めてできるのだから
素因数分解してから素因数を求めるというのは本末転倒．

ただ，全部調べるといっても
馬鹿正直に2から2613まで全部調べるのはやりすぎで
実際は
2から(2613)^{1/2}(2613の平方根のうちの正の方)までの
整数で素数であるものを順番に調べればいい．
そして，その範囲の整数が素数であるか一つ一つ調べるのは無駄で
先に，必要な範囲の素数をエラトステネスの篩で調べ上げておくとよい．

そうするとそれなりの速さで素因数分解はできる．

コンピュータで計算させるときはこんな方法でざっくりやってしまう．
これくらいなら慣れてれば，30分くらいもあればプログラムできると思う．
＃個人的にはこの手のプログラムはHaskelで書くのがよいと思う．

人間がやるなら，直観もあるから
思いついたらそれらしい数でやってみるというのは
まさに王道．

この回答へのお礼

素数てすごいですね。知識の量に脱帽です。全部調べるのは大変ですがその方法でしたら少し省略できるんですね。ありがとうございます。

お礼日時：2012/03/28 04:52

No.6 回答者： ta20000005 回答日時： 2012/03/28 01:46

もう答えが出ていますので、ちょっとおまけな話を。

ハーディが見つけた、2以上の自然数Nの最大の素因数を求める式が知られています。したがって、それでNを割って、その数で先の式をまた当てはめて、を繰り返せば、素因数分解できてしまいます。
ただし、その式で最大の素因数を求めることは素数列の一般項を使ってn番目の素数を求めるのと同じく意味がなく実用性もありませんが。

この回答へのお礼

面白いお話をありがとうございます。素数て不思議ですね。

お礼日時：2012/03/28 04:55

No.5 回答者： stomachman 回答日時： 2012/03/28 00:32

「全部調べる」とは言っても、もし2613を割り切る素数が存在するのなら、そのうちで最小のものは√(2613)=51.1… 以下です。

だから、51より小さい素数だけ、つまり高々十数個の素数pについて調べれば、素因数が（もしあれば）見つかることになります。

一般に、ある数nについて調べるには、√n以下の素数で割り切れるかどうかを調べます。
(1) もしどれでも割り切れなかったら元の数nは素数です。
(2) もし割り切れる素数pが見つかったら、その商（つまりその割り算の答）qが√q以下の素数で割り切れるかをどうか調べます。
これを繰り返せば良いのです。

　nがあまり大きな数でなく、また√n以下の素数の表を持っているのであれば、実際上、大した手間は掛かりません。しかしながら、nがたとえば何十桁という大きさになると手計算では到底やってられません。さらに大きくなると、コンピュータでも手に負えなくなります。

この回答へのお礼

実質５１以下！ですか。それならかなり楽になりますね。もっと桁が大きいと途方にくれます。素数て不思議ですね。有難うございました。

お礼日時：2012/03/28 04:54

No.4 回答者： Tacosan 回答日時： 2012/03/27 23:31

「素数かどうか」だけなら効率的な方法も存在するけど, 少なくとも今のところ素因数を見付ける効率的な方法は知られていない. つまり, 本質的には #1 の通り「全部試す」しかない.

まあ, このくらいの数字だとふるうかどうかも微妙だけど.

この回答へのお礼

素数て不思議ですね。このくらいの数字なら地道に探す手もありますが、大きな数字でもできるような仕組みなどが存在すると思ってしまいました。ありがとうございました。

お礼日時：2012/03/28 04:53

No.2 回答者： mojitto 回答日時： 2012/03/27 20:53

直感…ですかね。

2613を見たとき、なんとなく13の倍が26だなぁ～
13で割れるやん！…みたいに。
二桁まで分解できれば、九九からなんとかなりますよね。

この回答へのお礼

勘なんですね。ありがとうございます。

お礼日時：2012/03/28 04:44

No.1 回答者： Knotopolog 回答日時： 2012/03/27 20:07

２６１３を素因数分解すれば，それが答えです．

この回答へのお礼

ご回答ありがとうございました。

お礼日時：2012/03/29 21:49