2021年02月21日

素数プログラム

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









香港弾圧、抗議の署名1万超 日本政府に助け求める BLMパヨン沈黙

坂上忍、GACKTにブチギレ

なんで外国人って鯨を特別視してるの?

【悲報】ソニーさん、日本軽視した結果日本で築き上げたゲーム市場を失ってしまうw

時間を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
俺はサイトしか見てないから恐らく大丈夫だ



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がお送りします[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%死滅。みんな来て」

スクワットの効果ヤバすぎてワロタwwwwwww

【画像】アメリカの女子大生の飲み会、いい匂いがしそう

【オカルト研】ナチス魔女図書館が存在! ヒムラーが収集した1万3000冊とヒトラーも出席したオカルト儀式

【オカルト研】ナチス魔女図書館が存在! ヒムラーが収集した1万3000冊とヒトラーも出席したオカルト儀式

太平洋 中VS日米仏英独

コンビニ店員だが、見るからにキョロ充そうな奴がいたから圧力かけたwwwww

SNSのせいで日本は狂ってしまった

このシステム考え出したゲームって何?

森ノ宮とかいう大阪No.3の街www


気になるAmazonの本

雑談│19:51

 コメント一覧 (5)

    • 1. 名無しさん@まとめたニュース
    • 2021年02月21日 20:13
    • めっちゃよくあるナイーブな実装だと思うけど、
      なぜエラトステネスに勝てると思った?
    • 0
    • 2. 名無しさん@まとめたニュース
    • 2021年02月21日 20:15
    • うむ わからん
    • 0
      • 3. 名無しさん@まとめたニュース
      • 2021年02月21日 20:25
      • >>2
        ざっくり言うと、素数をリストに追加し、その追加したリストをループで処理で比較するから、数が大きくなるほど遅くなる
        定理を使えばルールが決まっているからリストの大きさに左右されない
      • 0
    • 4. 名無しさん@まとめたニュース
    • 2021年02月21日 22:02
    • 定義されてない変数を使わないでほしい
    • 0
    • 5. 名無しさん@まとめたニュース
    • 2021年02月22日 00:30
    • さっぱりわからんが、何故かこういうやりとりを読むのが好き
    • 0


コメントフォーム
記事の評価
  • リセット
  • リセット

コメントを投稿してくれる方へ
いくつかのエロい単語やURL等は使えません。
下記の投稿は無断で削除する場合があります。予めご了承ください。
・荒らし行為(宣伝行為含む)
・犯罪的なコメント
・差別的なコメント
・過激な下ネタ

他ブログのネタ満載 アンテナページへ


スポンサードリンク
記事検索
月別アーカイブ
QRコード
QRコード
読者登録
LINE読者登録QRコード
最新記事
スポンサードリンク