素数一覧を書き出すプログラム
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2005/10/25(火) 21:41:53アルゴリズムはエラトステネスの篩でいいよね。
っつーかそれ以外に素数一覧求めるいい方法知らないだけ。
00021
2005/10/25(火) 21:43:13int primes[] = {
#include "prime.dat"
}
ってできて何かと便利だろうし。
00031
2005/10/25(火) 21:49:00見つかった素数を一旦配列に格納しておいてからまとめてファイルに書き出すのとどっちが早い？
00041
2005/10/25(火) 21:51:380005デフォルトの名無しさん
2005/10/25(火) 21:52:25死ねば？
0006デフォルトの名無しさん
2005/10/25(火) 21:52:51その二つの方法の選択によって生じる速度差は、
アルゴリズムの改良／選定によって生じる速度差の1%には到達しないであろう
00071
2005/10/25(火) 22:06:25ファイル書き出しは別にやった方がいいか。
でも余計にメモリ食うな。
00081
2005/10/26(水) 00:28:45なんで？？
00091
2005/10/26(水) 01:01:00テンプレート関数の定義は宣言といっしょにしちゃうか。
0010デフォルトの名無しさん
2005/10/26(水) 01:01:02もちろん１００桁程度なら瞬殺するんだろうし、革命だな
0011デフォルトの名無しさん
2005/10/26(水) 02:27:440012デフォルトの名無しさん
2005/10/26(水) 02:56:40数学の公式集に出ている。それを使ったプログラムが
ベクターにいくつかあるぞ。
ちなみにエラトステネスはかなり遅いアルゴリズムだぞ。
00131
2005/10/26(水) 03:14:56とりあえずいったん配列に格納することにした。
00141
2005/10/26(水) 03:15:280015デフォルトの名無しさん
2005/10/26(水) 15:57:42奇数がそれ以下の素数で割れないならリストに追加
00161
2005/10/26(水) 18:32:45誰？
まあいいや。騙られた所で困るわけじゃない。
>>12
目的は2からNまでの素数列挙なので、
いちいち素数判定するよりは
エラトステネスの篩＋小手先高速化で行くのが良さそうな。
とりあえず2と3が素数で4が非素数であることを自明として、
6N±1についてだけ対象とすればいいですかね。
計算が簡単なのは奇数全部を対象とすることですが。
00171
2005/10/26(水) 18:36:342^32までの一覧を生成するとして素数がだいたい2億個になるから
誤判定率は最低でも1/2億でないと困りますよね。
んー
00181
2005/10/26(水) 18:41:050019デフォルトの名無しさん
2005/10/26(水) 22:12:44implicit none
integer :: i, j, nmax
logical, allocatable, dimension(:) :: lprm
read *, nmax
allocate(lprm(2:nmax))
lprm(2:nmax) = .true.
do i = 2, int(sqrt(real(nmax)))
if (lprm(i) == .false.) cycle
forall (j=i*2:nmax:i) lprm(j) = .false.
end do
do i = 2, nmax
if (lprm(i) == .true.) print *, i
end do
deallocate(lprm)
end program SieveOfEratosthenes
0020デフォルトの名無しさん
2005/10/27(木) 11:44:486N+1、6N+5(まぁ>16と同じことだが)で処理するなら奇数全部に比べて難しくないと思うが。
#-1は面倒でない?
■ このスレッドは過去ログ倉庫に格納されています