• ベストアンサー

菅野正人の素数生成方法は、多項式時間計算量？

菅野が下の動画に示した素数生成メカニズムを形式化した、菅野著『数字パズル　SeeK 10』などに於ける、エラトステネスの篩のアルゴリズムは、多項式時間内で素数を生成可能ですか。： https://www.youtube.com/watch?v=7u9NdEAOQaY

質問者が選んだベストアンサー

  • ベストアンサー
  • f272
  • ベストアンサー率46% (8021/17144)
回答No.1

可能です。 参考　https://algo-method.com/descriptions/64

koitiluv1842
質問者

お礼

早速の御回答を賜りまして、非常に有難く存じます。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. その他([技術者向] コンピューター)

関連するQ&A

  • 素数の生成アルゴリズムについてです。

    下記リンク内のアルゴリズムでは、多項式時間内に素数の生成が可能でしょうか。 なお、同スレ内には、他にも多々、素数生成アルゴリズムをコレクションしてありますので、出来ましたら、それらの時間計算量につきましても御教え下さい。 https://twitter.com/koitiluv1842/status/1500429851630931970

  • すばやく素因数分解する方法は？

    「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。

  • エラトステネスの篩(ふるい)について

    素数を求めるアルゴリズム「エラトステネスの篩(ふるい)」について質問があります。 Wikipedia によると http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9 【ステップ４】 探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。 と記載されています。 2～1000の間にある素数を調べる場合は、 素数リストの最大値が11のところで累乗が1000 を超えるため 残っている数が素数ということなります。 実際試してみたところ、493 を素数と見なしてしまいました。 493 は 17の倍数なのですが、上記のとおり素数リストの最大値が11のところで 残っている数を素数と考えると、17の倍数の削除が働きません。 ほかの質問でエラトステネスの篩(ふるい)について質問されている方がおられるようですが もうひとつ理解が足りませんでしたので、申し訳ありませんが 考え方、やり方の間違いなどについて、ご教授をお願いします。

  • 探索・整列アルゴリズムのメリット・デメリットについ

    「コンピューターはなぜ動くのか？」の第５章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1　主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)～(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。

  • 素数生成は、素数対数和グラフで多項式時間計算量？

    以下にリンクしました素数の対数の和のグラフについて、曲率を算定して、それから外挿して、任意の素数を生成する方法は、多項式時間内に素数を生成できますか。： https://twitter.com/Trianglemancsd/status/1546149996587847682

  • 素数生成は、小林吹代の公式では多項式時間計算量？

    Chat-bots で検索しても出ますが、下記の本にも暗示して有ります公式では如何でしょうか？ https://www.amazon.co.jp/-/en/gp/customer-reviews/R9SLEF6DAGMGY/ref=cm_cr_dp_d_rvw_ttl?ie=UTF8&ASIN=4297119366

  • YouTubeの再生数が全く増えない

    初めてYouTubeで動画を投稿してみて3日ほど経ったのですが、再生数が全く増えません。 タイトル・説明文・タグをしっかり入力し、一般公開にもしました。 が、再生数は全く増えず自分が確認で開いた回数だけ増えません。 3日も経って全く増えない事なんてあるんでしょうか？ 皆様から検索で出ないのか、まだ2つしか動画をアップしてないから、YouTubeのアルゴリズムで検索上位にでないのかとか色々原因を考えています。 よろしければ原因を教えてください。 また動画のリンクを張っておきますので宜しければ開いてみてください。 https://www.youtube.com/watch?v=CBkxzZvz2Sk

  • 素数生成 by エラトステネスの篩：多項式時間計算

    n*log(log(n)) < n^2 ∈ ｛多項式｝ なのですから、下記ウィキペディアの 「has an exponential time complexity （＝　指数関数的な時間計算量となる）」という記述は間違って居ますね？： https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

  • 生成多項式

    生成多項式、既約多項式とは何かを教えてください。 あと、擬似乱数係数とは何かも教えてください。 それからできればKASAMI係数とは何かも教えてください。

  • 素数生成は、リーマン予想派生関数で、多項式時間計算

    リーマン予想（RH）は、ツイッターの @koitiluv1842 の RH 乃至 RHT で検索なさると出ます証明たちがありますが、それなしでも、数値計算による擬似・証明の例が１０兆もありますので、下記の本に有りますような関数で、多項式時間内に素数生成が出来ますでしょうか。 https://twitter.com/koitiluv1842/status/1559385231718658049

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する