素数プログラム

1 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:20:57.798 ID:JIX5od2P0.net

これ↓も結構いいアルゴだと思ったんだけどエラトステネスの篩には敵わんか？

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,[])

2 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:22:30.117 ID:58IUIhRh0.net

そこそこの精度だけど
エラトステネスのふるいよりも速い
アルゴリズムあるよね

3 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:23:38.685 ID:JIX5od2P0.net

そうなのか
そこら辺詳しくないわ

4 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:24:59.585 ID:58IUIhRh0.net

高校数学の美しい物語でも紹介されてた気がする

5 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:26:30.525 ID:JIX5od2P0.net

それなら読んだことあるかも知れない
まぁ俺はそんなに大きい素数は必要ないしな…

6 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:27:35.887 ID:BgenxLJc0.net

そのプログラムもエラトステネスのふるいになってない？
平方根までのチェックのが早いだろうけど

7 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:32:54.736 ID:JIX5od2P0.net

>>6
そうなのかな？
素数のリストを作っていって、今まで出た素数で割れないものを新たに素数リストに加えるって感じだけど
エラトステネスの篩はとにかく倍数を消してく感じだよね

8 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:46:28.579 ID:iRvq4w8N0.net

>>7
「消す」の代わりに「わざわざ毎回計算する」ってだけで、やってることは同じだろ

9 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:48:11.179 ID:JIX5od2P0.net

そうだろうか…
計算量は同じ？

10 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:50:54.058 ID:iRvq4w8N0.net

計算量自体は同じじゃね？
ただし、エラトステネスは目標となる数までのテーブルを一気に確保するのに対して、
>>1の場合は動的確保により要素数を増やし続けるから、
その分のコストが差として出る

11 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:52:18.932 ID:BgenxLJc0.net

計算量は同じO(n^2)だと思う
ミラーラビンは
確率4の-k乗の精度でO(k*log3 n)らしい

12 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:55:44.968 ID:JIX5od2P0.net

ふむ…そうかも
調べたらエラトステネスの篩の計算量はO(nloglogn)らしい
>>1も同じかなぁ

13 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 17:59:53.693 ID:BgenxLJc0.net

素数の頻度はloglognに近似するのか

14 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:01:54.324 ID:JIX5od2P0.net

https://mathtrain.jp/eratosthenes

これを読む限り、mまでの素数を求める計算量は

エラトステネス=Σ[p<√m](m/p)
>>1=Σ[k=2,m]Σ[p<√k]1

という感じだな

15 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:02:44.692 ID:JIX5od2P0.net

>>1ではルート使ってなかったけど使ったものと想定してくれ

16 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:04:49.203 ID:BgenxLJc0.net

ああ頻度が近似するんじゃなくてルート使うからかそうだな

17 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:08:25.864 ID:mZ33aBbi0.net

割り算自体は掛け算より遅いし
ループ上限は平方根で十分

エラトステネスの方が速いだろうな

18 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:08:31.737 ID:JIX5od2P0.net

うむ

19 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:11:17.237 ID:JIX5od2P0.net

「素数定理」によればn以下の素数の個数はn/lognで近似できるらしいから

>>1の計算量
=Σ[k=2,m]Σ[p<√k]1
=Σ[k=2,m]2√k/logk
=

わからん

20 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:13:08.409 ID:58IUIhRh0.net

>>5
サイトの方な

21 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:16:28.284 ID:JIX5od2P0.net

>>20
俺はサイトしか見てないから恐らく大丈夫だ

22 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:16:47.280 ID:JIX5od2P0.net

まぁいいや
お前ら付き合ってくれてありがと

23 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:19:47.335 ID:mZ33aBbi0.net

動的に上限を増やすなら
回転ふるいを応用すれば
それなりの速度を保ちつつメモリ使用量を抑えられるかもね

確定探索の話ね。
勿論確率的探索なら話は違う

24 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:21:36.601 ID:JIX5od2P0.net

よく分からんけどthx

25 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:29:42.509 ID:mZ33aBbi0.net

長さ6の回転ふるいを使う場合

6以上の素数は全て、6n+1と6n+5の形になるから
この形の数のみを判定すれば良い

メモリに合わせてこの回転ふるいを
大きくする、的な話

サイズは小さい素数全ての積ね
6,30,210.…

26 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 18:43:09.869 ID:JIX5od2P0.net

なるほど、分かりやすい

27 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 19:17:20.459 ID:BgenxLJc0.net

わかりやすい

28 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 19:21:58.229 ID:/7sq4KMF0.net

改良は可能だけど基本的にはエラトステネスの篩の計算量O(nloglogn)が最速

29 ：以下、？ちゃんねるからVIPがお送りします：2020/10/27(火) 19:49:46.744 ID:mZ33aBbi0.net

一応、アトキンの方が理論上は速いらしいが
実装してエラトステネスと差が出るのは
かなり大きな数になるらしい