エラトステネスの篩の実装
エラトステネスの篩と、それを利用した素因数の高速列挙の実装をライブラリ化した。(どちらかというと後者の実装を残す目的で作った)
前提
高速素因数分解
- エラトステネスの篩でnまでの整数を素数判定する過程で、各値の最小の素因数をテーブル
min_prime_factor
に保存しておく x / min_prime_factor[x]
でxの約数が得られるので、値xの最小の素因数を確認すると同時に、xをその約数に上書きする- 上記をxが1になるまでの間繰り返すことで素因数を列挙できる
- ループ回数は高々log x回なので、O(log x)
検証用問題
実装
/// エラトステネスの篩 struct Eratosthenes { vector<bool> is_prime; /// nまでの素数一覧 vector<int> primes; /// 整数xの最小の素因数 vector<int> min_prime_factor; Eratosthenes(const int n) { min_prime_factor.resize(n + 1); /// nまでの素数一覧 is_prime.assign(n + 1, true); is_prime[0] = is_prime[1] = false; min_prime_factor[0] = min_prime_factor[1] = 1; for (int i = 2; i <= n; i++) { if (is_prime[i]) { for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; if (min_prime_factor[j] == 0) min_prime_factor[j] = i; } primes.push_back(i); min_prime_factor[i] = i; } } } /** * xの素因数の種類を取得 * @param x n以下の数値を指定する必要がある */ set<int> get_prime_factors(int x) { set<int> s; while (x > 1) { s.insert(min_prime_factor[x]); x /= min_prime_factor[x]; } return s; } /** * xの素因数とその数を取得 * @param x n以下の数値を指定する必要がある */ map<int, int> get_prime_factor_and_cnt(int x) { map<int, int> mp; while (x > 1) { mp[min_prime_factor[x]]++; x /= min_prime_factor[x]; } return mp; } };