素数列挙について - MugiCha

Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A

[matarillo]

アトキンのふるい

[antimon2_math]

Atkinの篩は実装してみたいなー。

[yuske711]

素数列挙高速化まとめ

[yysaki]

素数列挙高速化まとめ

[nitoyon]

素数列挙方式いろいろ。Eratosthenesの篩、Wheel factorization、区間篩、Atkinの篩。

[mnshtn]

昔、素数を初めて学んだ頃、はまってたなぁ。

[harapon1012]

めっちゃ勉強になる

[sucrose]

面白い！あとは確率的な方法？

[kakeru_13493]

こういうのが好き