タグ

algorithmとnumber-theoryに関するnabinnoのブックマーク (4)

  • 篩法 - Wikipedia

    篩法(ふるいほう)、または単に篩(ふるい)とは、数論でよく使う技法の総称である。 整数をふるった集合 (sifted set) の元の個数を数えたり、その大きさを評価したりする。篩の操作によって得られる集合の例として、ある数を超えない素数の集合が挙げられる。つまりいにしえのエラトステネスの篩、あるいは一般にルジャンドルの篩と呼ばれるものである。しかしこれらの篩を直接用いた素数分布の定量的研究は、誤差項の累積というどうしようもない困難に直面した。20世紀に入り、双子素数予想やゴールドバッハ予想などの研究の中でこれらの困境を克服する方法が見いだされ、現在ではブルンの篩をはじめ、セルバーグの篩、大きな篩といったものが編み出されている。 これらの原始的なエラトステネスの篩の発展形においては、ふるわれた(評価されるべき)集合を、他の解析しやすいより単純な集合によって近似することや、sieving f

  • 素数探索アルゴリズムで遊ぶ

    (初出: はじめての Go 言語 (on Windows) その2 - Qiita) Go 言語は公式のドキュメントがとても充実していて(ただしほぼ英語だけど),私のような初学者に易しい環境といえる。 Documentation - The Go Programming Language : 言語仕様に関するドキュメントはこちら(一部日語化されている) Packages - The Go Programming Language : 標準パッケージのドキュメントはこちら(一部日語化されている) とはいえ,コードが実際にどのように機能するかは書いてみないと分からない部分もある。 なので,今回からは実際にコードを書きながら言語の癖のようなものを調べていくことにする。 仕事に使うなら厳密な評価が必要だけど,今のところはそんな予定もないし,まずはテキトーで(笑) 早速,みんな大好き素数探索アル

    素数探索アルゴリズムで遊ぶ
  • エラトステネスの篩 - Wikipedia

    この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。

    エラトステネスの篩 - Wikipedia
  • Sieve of Atkin - Wikipedia

    In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and

  • 1