Skip to content →

線形篩

\(N\) 以下の素数を線形時間 \(O(N)\) で列挙する篩(ふるい)を解説します。Atkin の篩という時間 \(O(N/\log\log N)\)、空間 \(O(N^{1/2+O(1)})\) で動作する、より高速な篩も存在しますが、それと比べて実装が簡単で、更に \(N\) 以下の自然数に対する最小の素因数が列挙されるという利点があります。特に後者の性質は、素因数分解や冪乗の列挙に応用できて面白いと思います。

線形篩の解説

素因数分解したときに \(x = p_1^{e_1} p_2^{e_2} \ldots p_n^{e_n} \ (p_1 < p_2 < \ldots < p_n)\) となる合成数 \(x\) について、Eratosthenes の篩だと \(p_1, p_2, \ldots, p_n\) の全ての素因数で \(x\) を篩いに掛けて合成数と判断していました。そこで線形篩では最小の素因数 \(p_1\) のみで \(x\) を篩に掛け合成数と判断することで計算量を削減します。これは、\(p_1\) で篩うとき、最小素因数が \(p_1\) 以上の自然数 \(d\) との積 \(p_1 d\) だけを篩う対象にすればよいです。Python のコードにすれば下のようになります。最小素因数は各数に対してただ一つですから、各自然数は1回しか篩われません。つまり、計算量は \(O(N)\) です。

N = 10 ** 5
prime_list = [] # 発見した素数のリスト
min_prime_factor = [None] * (N + 1) # 発見した最小素因数。
for d in range(2, N):
    if min_prime_factor[d] is None:
        min_prime_factor[d] = d
        prime_list.append(d)
    for p in prime_list:
        if p * d > N or p > min_prime_factor[d]:
            break
        min_prime_factor[p * d] = p

線形篩を用いた冪数の列挙

線形篩を用いると、\(m\) を法とする冪数 \(1^k, 2^k ,\ldots, N^k\) の列挙が \(O\left(N\frac{\log m}{\log N}\right)\) でできます。線形篩で \(N\) 以下の数に対する最小素因数と、\(N\) 以下の素数を \(O(N)\) で列挙しておきます。素数に対しては 冪数を繰り返し二乗法で求めます。 素数定理より \(N\) 以下の素数は \(O(N/\log N)\) 個あるので、この列挙は \(O\left(N\frac{\log m}{\log N}\right)\) で行えます。 合成数 \(x\) はどうすれば良いでしょうか。最小素因数 \(p_1\) を使って部分問題に分解しましょう! 小さい合成数から順に冪乗を計算していきます。 \(x^k=p_1^k\cdot\left(\frac{x}{p_1}\right)^k\) のうち、 \(p_1\) は素数なので冪乗はすでに計算しています。\(\frac{x}{p_1}\) は \(x\) 未満の素数または合成数なのでこちらもすでに冪乗は計算してあります。併せると素数の累乗を計算しておけば \(O(N)\) で合成数の場合は冪乗が列挙できました。以上で冪乗の列挙が \(O\left(N\frac{\log m}{\log N}\right)\) で行えました。

線形篩を用いた合成数を法とする逆元の列挙

線形篩を用いると、合成数 \(m\) を法とする \(N\) 以下の逆元の列挙が \(O\left(N\right)\) でできます。アルゴリズムは冪乗の列挙と似ています。まず線形篩で \(N\) 以下の数の最小素因数を列挙しておきます。素数の逆元については互除法で求めます。一回あたり \(O(\log N)\) 掛かりますが、\(N\) 以下の素数は \(O(N/\log {N})\) 個しかないので全体では \(O\left(N\right)\) です。合成数 \(x\) についてはその最小素因数 \(p_1\) を用いて \(x^{-1}=p_1^{-1}\cdot(x/p_1)^{-1}\) とすれば \(O(1)\) で求まります。以上で逆元の列挙が \(O\left(N\right)\) でできました。

冪乗の列挙の高速化は Min_25 さんに教えていただきました。逆元の列挙の計算量解析は maspy さんに助けてもらいました。他にも応用がありそうな考え方です。

Published in アルゴリズム

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA