アカウント名:
パスワード:
とりあえず、手計算で出来る範囲（10以下）で試してみたところ、1で始まる素数は1つもありませんでした。
# 心が落ち着きました。
もうちょっと頑張って20以下まで調べてみたところ、1で始まる素数の出現率は50%でした。# だんだんわかってきました?
自分の限界に挑戦すべく30以下まで調べてみたところ、1で始まる素数の出現率は40%でした。
// むむっなにか掴みかけてきたぞっ(:>^
直感的には桁の限界までの範囲で全部数えれば、どれも1/9、つまり11％になりそうな気がした。素数は違うか。
999までの範囲で数えてみた。1：25 （0.149）2：19 （0.113）3：19 （0.113）4：20 （0.119）5：17 （0.101）6：18 （0.107）7：18 （0.107）8：17 （0.101）9：15 （0.089）
次に9999までの範囲で数えてみた。1：160 （0.130）2：146 （0.119）3：139 （0.113）4：139 （0.113）5：131 （0.106）6：135 （0.109）7：125 （0.101）8：127 （0.103）9：127 （0.103）
> ##ベストエフォートより、リーストエフォットベンフォードより... と空目した。
＞ 末尾が2の素数なんて
お前は1個あるだけマシじゃないかと、4,6,8は声をそろえて言いました。
可哀そうな、0 はどちらからも相手にされませんでした・・・
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。
フルイの分割というのは、フルイの対象とする範囲を、例えば
2～10^810^8～2*10^82*10^8～3*10^8 ....99*10^8～100*10^8
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。）
途中の数からフルイを計算をはじめるためには、素数の表を持っておく必要があります。10^10までフルイを実行するには10^5までの素数表を持っておけばいいです。これはあらかじめ作る必要はなく、最初の2～10^8のフルイ実行時の結果を記憶しておけばいいです。
というような工夫をすれば、AMD Opteron 1216で10^10までのフルイは3分7秒、10^11までは34分7秒で実行出来ました。
なおメモリ節約のため上記のような分割ではなく、bit単位でのアクセス、2/3/5の倍数を例外扱いなどをしてメモリ節約される方もいるかもしれませんが、かなりペナルティが高いです。10^10までのフルイで24分57秒、10^11までのフルイで230分16秒という結果になりました。
言語は何で書きましたか？
3や5でペナルティが大きいのはなんとなく分かる気がします。しかし2は単純な論理積演算で検証が可能ですが、それでもペナルティは大きいんですか？
2/3/5でそれぞれ比較は行っていませんが、10^9までの計算で次のような結果になっています。(10^10までは行ってません)
bit単位のアクセスでメモリ節約: 2分20秒bit単位のアクセスに加えて2/3/5の例外扱いでメモリ節約: 2分59秒
したがって2/3/5の例外扱いでペナルティが高いは大げさでした。bit単位でのアクセスはペナルティが高いに修正します。
なお、2/3/5の例外扱いのために次のような読み替えテーブルを使ってます。説明は省きますが2/3/5の最小公倍数は30ですので、大体意味わかると思います。
static const int_fast32_t yomikae_table[30]={-1, 0,-1,-1,-1,-1,-1, 1,-1,-1, -1, 2,-1, 3,-1,-1,-1, 4,-1, 5, -1,-1,-1, 6,-1,-1,-1,-1,-1, 7};
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
人生unstable -- あるハッカー
こ、これは (スコア:0)
みんな、すぐに手元のコンピュータで確認してみるんだ
エラトステネスの篩をアレンジしたプログラムなんかは簡単に作れるよね
落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:5, おもしろおかしい)
とりあえず、手計算で出来る範囲（10以下）で試してみたところ、1で始まる素数は1つもありませんでした。
# 心が落ち着きました。
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:3, 興味深い)
もうちょっと頑張って20以下まで調べてみたところ、1で始まる素数の出現率は50%でした。
# だんだんわかってきました?
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:4, おもしろおかしい)
自分の限界に挑戦すべく30以下まで調べてみたところ、1で始まる素数の出現率は40%でした。
// むむっなにか掴みかけてきたぞっ(:>^
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:2)
直感的には桁の限界までの範囲で全部数えれば、どれも1/9、つまり11％になりそうな気がした。素数は違うか。
999までの範囲で数えてみた。
1：25 （0.149）
2：19 （0.113）
3：19 （0.113）
4：20 （0.119）
5：17 （0.101）
6：18 （0.107）
7：18 （0.107）
8：17 （0.101）
9：15 （0.089）
次に9999までの範囲で数えてみた。
1：160 （0.130）
2：146 （0.119）
3：139 （0.113）
4：139 （0.113）
5：131 （0.106）
6：135 （0.109）
7：125 （0.101）
8：127 （0.103）
9：127 （0.103）
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:1)
> ##ベストエフォートより、リーストエフォット
ベンフォードより... と空目した。
Re: (スコア:0)
# 末尾が2の素数なんて
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:2)
＞ 末尾が2の素数なんて
お前は1個あるだけマシじゃないかと、4,6,8は声をそろえて言いました。
可哀そうな、0 はどちらからも相手にされませんでした・・・
エラトステネスの篩で参考 (スコア:5, 参考になる)
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。
フルイの分割というのは、フルイの対象とする範囲を、例えば
2～10^8
10^8～2*10^8
2*10^8～3*10^8
....
99*10^8～100*10^8
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。）
途中の数からフルイを計算をはじめるためには、素数の表を持っておく必要があります。10^10までフルイを実行するには10^5までの素数表を持っておけばいいです。これはあらかじめ作る必要はなく、最初の2～10^8のフルイ実行時の結果を記憶しておけばいいです。
というような工夫をすれば、AMD Opteron 1216で10^10までのフルイは3分7秒、10^11までは34分7秒で実行出来ました。
なおメモリ節約のため上記のような分割ではなく、bit単位でのアクセス、2/3/5の倍数を例外扱いなどをしてメモリ節約される方もいるかもしれませんが、かなりペナルティが高いです。10^10までのフルイで24分57秒、10^11までのフルイで230分16秒という結果になりました。
Re:エラトステネスの篩で参考 (スコア:2, おもしろおかしい)
Re:エラトステネスの篩で参考 (スコア:1)
言語は何で書きましたか？
Re:エラトステネスの篩で参考 (スコア:2)
Re: (スコア:0)
3や5でペナルティが大きいのはなんとなく分かる気がします。
しかし2は単純な論理積演算で検証が可能ですが、それでも
ペナルティは大きいんですか？
Re:エラトステネスの篩で参考 (スコア:2)
2/3/5でそれぞれ比較は行っていませんが、10^9までの計算で
次のような結果になっています。(10^10までは行ってません)
bit単位のアクセスでメモリ節約: 2分20秒
bit単位のアクセスに加えて2/3/5の例外扱いでメモリ節約: 2分59秒
したがって2/3/5の例外扱いでペナルティが高いは大げさでした。
bit単位でのアクセスはペナルティが高いに修正します。
なお、2/3/5の例外扱いのために次のような読み替えテーブル
を使ってます。説明は省きますが2/3/5の最小公倍数は30です
ので、大体意味わかると思います。
static const int_fast32_t yomikae_table[30]=
{-1, 0,-1,-1,-1,-1,-1, 1,-1,-1,
-1, 2,-1, 3,-1,-1,-1, 4,-1, 5,
-1,-1,-1, 6,-1,-1,-1,-1,-1, 7};
Re: (スコア:0)
100万は64ビットでも桁あふれしたので、10万まで。
1 20.54%
2 17.45%
3 15.01%
4 12.78%
5 10.70%
6 8.61%
7 6.79%
8 4.94%
9 3.18%
ちなみに、素数の出現率ではなく、素数の出現率の和です、念のため。
Re: (スコア:0)
○ 出現数の和の割合
あと、9の割合って減って行く様な気がするが、
桁を上げて行くと増えて行くんですよね。不思議。