素数を自動的に作る

Question

２から順番に無限に素数を作り続けるソフトはどこかにありますか。
実はゴールドバッハの予想
「すべての偶数は二つの素数の和で表される。」
が非常に気になりまして今日まで４００ぐらいまでは実証したのですがこれが１万を超えるととても私のキャパでは対応できません。
　せめて数字を入れたら素因数分解をしてくれるソフトなんてありませんか？

kmee · Accepted Answer

ある正の整数n以下の全ての素数を求めるのに、「エラトステネスのふるい」という有名な方法があります。
VBAでも簡単に作れます。
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

コンピュータが有限なので、無限に作りつづけることはできませんが、メモリの許す限りの素数を求めることができます。

> 数字を入れたら素因数分解をしてくれるソフト

とありますが、これって次のような方法で調べようとしていませんか?

・調べる偶数をmとする
・m=p+q (p,qは正の整数)とする
・pを素因数分解する。→素数かどうか判断できる
・qを素因数分解する。→素数かどうか判断できる

素因数分解は計算に時間がかかります。
先に素数一覧をふるいで求めておいて、 p,q2つの組み合わせをが m=p+qになるか調べる方が効率がよいと思います。
また、完成した素数一覧は、次の偶数m+2について調べる際にも利用できます。

既にある程度までは確認済だとしても、プログラムを考えるのは面白いものなので、挑戦してはいかがでしょうか

ki073 · Answer

No.2です。
Linuxだとfactorという素因数分解するコマンドがあります。
1万までの奇数の素因数分解をしたところ、10秒程度で全部できました。結構速いです。

Windowsだとこのあたりで手に入るかもしれません。
http://www.asahi-net.or.jp/~kc2h-msm/mathland/matha1/howto.htm

Cのプログラムは
http://d.hatena.ne.jp/kenjiaiko/20071213/1197574602
のあたりで、結構速そうですね。

ki073 · Answer

多分自分で作るしかないと思います。

倍精度浮動小数点なら十進数で15桁程度、Cなどなら8バイトの整数がサポートされていますので20桁程度まで精度をだせますので、注意深くプログラムを作成すればこの程度の精度で計算可能です。また多倍長整数をサポートしたスクリプト言語やライブラリを使えばもっと桁数の多い整数の計算も可能です。

Rubyで素数を求めるプログラムを作成したことがありますが、アルゴリズムを工夫しないと結構時間がかかります（Rubyは多倍長整数が使える）。素数和になる組み合わせを見つける方が時間がかかりそうですが、速度を気にしなければ簡単に作れます。

DOUGLAS_ · Answer

＞実はゴールドバッハの予想が非常に気になりまして
＞今日まで４００ぐらいまでは実証した
　それはそれは、どうもお疲れ様でございました。
　　<(_ _)>

＞１万を超えるととても私のキャパでは対応できません。
　モチベーションを下げるようで恐縮ですが、
●ゴールドバッハの予想
http://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%90%E3%83%83%E3%83%8F%E3%81%AE%E4%BA%88%E6%83%B3
に
-- ここから引用 ---------------------------
この予想は、2007年2月現在、5×10^17 までの全ての偶数について成り立つことが、コンピュータによって確かめられている。
-- ここまで引用 ---------------------------
と出ています。

5×10^17 = 500,000,000,000,000,000
ですから、50京（50兆の1万倍、50億の1億倍）まで
＞成り立つことが・・・確かめられている。
とのことです。

＞せめて数字を入れたら素因数分解をしてくれるソフトなんてありませんか？
とのことですので、「どうしても」ということでしたら、下記あたりをご覧ください。

ただし、「5×10^17」を計算できるような代物は、簡単には手に入らないかとは存じますが。。。。

●素因数分解 ソフト
http://www.google.co.jp/search?q=%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3+%E3%82%BD%E3%83%95%E3%83%88

●素因数分解 プログラム
http://www.google.co.jp/search?q=%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3+%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0

●素因数分解 アルゴリズム
http://www.google.co.jp/search?q=%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%20%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

素数を自動的に作る

ある正の整数n以下の全ての素数を求めるのに、「エラトステネスのふるい」という有名な方法があります。

No.2です。

多分自分で作るしかないと思います。

＞実はゴールドバッハの予想が非常に気になりまして

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング