min25筛と洲閣筛
min25筛
ある積性関数 f(x) が与えられ、f(p) が素数 p に関する多項式で、かつ f(pk) が高速に計算できる場合、sumi=1n f(i) を求める。
例：n = 1010 に対して sumi=1n σ0(ik) を求める。
ステップ1：素数の積性関数の前処理和
1 から n までの素数の個数を求める。
f(n, m) を、2 から n までの数のうち、素数であるか、または最小の素因数が p1, ..., pm (pi は i 番 ...
6月1日 21:05 投稿