- これ↓も結構いいアルゴだと思ったんだけどエラトステネスの篩には敵わんか？
def sosulist(m):
def sosulist_(n,ls):
if n>=m:
return ls
else:
for p in ls:
if not n%p:
break
else:
ls.append(n)
return sosulist_(n+1)
return sosulist_(2,[]) - そこそこの精度だけど
エラトステネスのふるいよりも速い
アルゴリズムあるよね - そうなのか
そこら辺詳しくないわ - 高校数学の美しい物語でも紹介されてた気がする
- それなら読んだことあるかも知れない
まぁ俺はそんなに大きい素数は必要ないしな… - >>5
サイトの方な - >>20
俺はサイトしか見てないから恐らく大丈夫だ - そのプログラムもエラトステネスのふるいになってない？
平方根までのチェックのが早いだろうけど - >>6
そうなのかな？
素数のリストを作っていって、今まで出た素数で割れないものを新たに素数リストに加えるって感じだけど
エラトステネスの篩はとにかく倍数を消してく感じだよね - >>7
「消す」の代わりに「わざわざ毎回計算する」ってだけで、やってることは同じだろ - そうだろうか…
計算量は同じ？ - 計算量自体は同じじゃね？
ただし、エラトステネスは目標となる数までのテーブルを一気に確保するのに対して、
>>1の場合は動的確保により要素数を増やし続けるから、
その分のコストが差として出る - 計算量は同じO(n^2)だと思う
ミラーラビンは
確率4の-k乗の精度でO(k*log3 n)らしい - ふむ…そうかも
調べたらエラトステネスの篩の計算量はO(nloglogn)らしい
>>1も同じかなぁ - 素数の頻度はloglognに近似するのか
- https://mathtrain.jp/eratosthenes
これを読む限り、mまでの素数を求める計算量は
エラトステネス=Σ[p<√m](m/p)
>>1=Σ[k=2,m]Σ[p<√k]1という感じだな
- >>1ではルート使ってなかったけど使ったものと想定してくれ
- ああ頻度が近似するんじゃなくてルート使うからかそうだな
- 割り算自体は掛け算より遅いし
ループ上限は平方根で十分エラトステネスの方が速いだろうな
- うむ
- 「素数定理」によればn以下の素数の個数はn/lognで近似できるらしいから
>>1の計算量
=Σ[k=2,m]Σ[p<√k]1
=Σ[k=2,m]2√k/logk
=わからん
- まぁいいや
お前ら付き合ってくれてありがと - 動的に上限を増やすなら
回転ふるいを応用すれば
それなりの速度を保ちつつメモリ使用量を抑えられるかもね確定探索の話ね。
勿論確率的探索なら話は違う - よく分からんけどthx
- なるほど、分かりやすい
素数プログラム
VIP
コメント