素数 "列挙" アルゴリズムを極めるスレ
■ このスレッドは過去ログ倉庫に格納されています
0379Delフサギコ ◆A6VzDeLphI
NGNG∧,,∧ / 試行錯誤したり
ミ,,゚Д゚彡 < 実装したりして、いろいろ
,;゙ ミ \ わかってくるものっすね。
@ミ,,,UUミ  ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
1-100で、Excelで手動でふつってみてわかったですが
リンク先の所に書いてあるメモリ消費の問題
バカ正直に1-100の入れ物を用意した場合を100として
篩の箱を
2の倍数消したら当然残りが50箱でメモリ消費半分50%
3の倍数消したら残り2/3でそれを2の倍数ので割ってメモリ消費1/3 33%
5の倍数消したら(4/5)*(2/3)*(1/2)=(4/15)=26....%
7の倍数消したら(6/7)*(4/5)*(2/3)*(1/2)=(8/35)=22....%
11の倍数消したら(10/11)*(6/7)*(4/5)*(2/3)*(1/2)=(16/77)=20.7....%
くらいの効率っすか。11まで事前に圧縮かけていても270MBの1/5程度にしか
ならないから、int32最大までの素数を求める篩は
55MB程度のメモリは必要っすね。
2,3,5倍数消ししたクラス2,3,5,7を消したクラスを作成して
比較してみたのですが
メモリ消費量は減りますが
計算速度は高速化してないようでした。
■ このスレッドは過去ログ倉庫に格納されています