osa_k法
(math/prime/osa_k.hpp)

• View this file on GitHub
• Last update: 2020-12-06 13:40:38+09:00
• Include: #include "math/prime/osa_k.hpp"
• Link: https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409

概要

$n$以下の素因数分解・素数判定を高速に行う.

計算量

• 前処理 : $O(n\log\log{n})$
• クエリ
  • 素因数分解 : $O(\log{n})$
  • 素数判定 : $O(1)$

使用例

• osa_k pm(n) : $n$以下の自然数に対して求める.
• pm.prime_factor(x) : $x$を素因数分解.
• pm.is_prime(x) : $x$を素数判定.

Verified with

• test/aoj/ALDS1_1_C.osa_k.test.cpp

Code

/**
* @brief osa_k法
* @docs docs/math/prime/osa_k.md
* @see https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409
*/

struct osa_k {
    int N;
    vector<int> min_prime;
    osa_k(int _N)
        : N(_N + 1), min_prime(N) {
        iota(min_prime.begin(), min_prime.end(), 0);
        for (int p = 2; p * p <= N; ++p) {
            if (min_prime[p] != p) continue;
            for (int i = 2 * p; i <= N; i += p) {
                if (min_prime[i] != i) continue;
                min_prime[i] = p;
            }
        }
    }
    bool is_prime(int x) {
        assert(x <= N);
        if (x <= 1) return false;
        return min_prime[x] == x;
    }
    map<int, int> prime_factor(int x) {
        assert(x <= N);
        map<int, int> pf;
        while (x > 1) {
            pf[min_prime[x]]++;
            x /= min_prime[x];
        }
        return pf;
    }
};

#line 1 "math/prime/osa_k.hpp"
/**
* @brief osa_k法
* @docs docs/math/prime/osa_k.md
* @see https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409
*/

struct osa_k {
    int N;
    vector<int> min_prime;
    osa_k(int _N)
        : N(_N + 1), min_prime(N) {
        iota(min_prime.begin(), min_prime.end(), 0);
        for (int p = 2; p * p <= N; ++p) {
            if (min_prime[p] != p) continue;
            for (int i = 2 * p; i <= N; i += p) {
                if (min_prime[i] != i) continue;
                min_prime[i] = p;
            }
        }
    }
    bool is_prime(int x) {
        assert(x <= N);
        if (x <= 1) return false;
        return min_prime[x] == x;
    }
    map<int, int> prime_factor(int x) {
        assert(x <= N);
        map<int, int> pf;
        while (x > 1) {
            pf[min_prime[x]]++;
            x /= min_prime[x];
        }
        return pf;
    }
};

Back to top page