素数プログラム
これ↓も結構いいアルゴだと思ったんだけどエラトステネスの篩には敵わんか？
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,[])
香港弾圧、抗議の署名1万超 日本政府に助け求める BLMパヨン沈黙
坂上忍、ＧＡＣＫＴにブチギレ
なんで外国人って鯨を特別視してるの？
【悲報】ソニーさん、日本軽視した結果日本で築き上げたゲーム市場を失ってしまうｗ
時間を15分巻き戻すor15分停止するor15分スキップする
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
それなら読んだことあるかも知れない
まぁ俺はそんなに大きい素数は必要ないしな…
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
俺はサイトしか見てないから恐らく大丈夫だ
それなら読んだことあるかも知れない
まぁ俺はそんなに大きい素数は必要ないしな…
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
俺はサイトしか見てないから恐らく大丈夫だ
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
「消す」の代わりに「わざわざ毎回計算する」ってだけで、やってることは同じだろ
そのプログラムもエラトステネスのふるいになってない？
平方根までのチェックのが早いだろうけど
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がお送りします[sage] ：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
=
わからん
22 ： 以下、？ちゃんねるからVIPがお送りします ：2020/10/27(火) 18:16:47.280 ID:JIX5od2P0.net
まぁいいや
お前ら付き合ってくれてありがと
23 ： 以下、？ちゃんねるからVIPがお送りします[sage] ：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がお送りします[sage] ：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がお送りします[sage] ：2020/10/27(火) 19:49:46.744 ID:mZ33aBbi0.net
一応、アトキンの方が理論上は速いらしいが
実装してエラトステネスと差が出るのは
かなり大きな数になるらしい
【悲報】酒飲めない人が手軽に気持ちよくなる方法無い
観光客減で瀕死の草津温泉が苦し紛れの研究結果を発信「草津温泉の湯でコロナ99%死滅。みんな来て」
スクワットの効果ヤバすぎてワロタｗｗｗｗｗｗｗ
【画像】アメリカの女子大生の飲み会、いい匂いがしそう
【オカルト研】ナチス魔女図書館が存在！ ヒムラーが収集した1万3000冊とヒトラーも出席したオカルト儀式
【ｵｶﾙﾄ研】ナチス魔女図書館が存在！ ヒムラーが収集した1万3000冊とヒトラーも出席したオカルト儀式
太平洋 中VS日米仏英独
コンビニ店員だが、見るからにキョロ充そうな奴がいたから圧力かけたｗｗｗｗｗ
SNSのせいで日本は狂ってしまった
このシステム考え出したゲームって何？
森ノ宮とかいう大阪No.3の街ｗｗｗ
気になるAmazonの本
雑談│19:51
なぜエラトステネスに勝てると思った？