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 投稿
線形ふるい法による素数、オイラー関数、メビウス関数の高速計算
線形ふるい法 (Linear Sieve)
線形ふるい法は、ある範囲内の素数を効率的に求めるアルゴリズムです。このアルゴリズムの時間計算量はO(n)であり、各合成数が一度だけふるい落とされることを保証します。本稿では、線形ふるい法を用いて素数、オイラー関数、メビウス関数を計算する方法を解説します。
1. 素数の線形ふるい
素数の線形ふるいは、指定された上限Nまでのすべ ...
5月18日 22:09 投稿