math/osak.hpp

• View this file on GitHub
• Last update: 2023-02-06 23:12:05+09:00
• Include: #include "math/osak.hpp"

Verified with

• verify/aoj_alds1/aoj_alds1_1_c_osa_k.test.cpp

Code

#pragma once

struct Osak {
    int n;
    std::vector<int> min_factor;

    Osak(int n) : n(n), min_factor(n + 1) {
        std::iota(min_factor.begin(), min_factor.end(), 0);
        if (n >= 0) min_factor[0] = -1;
        if (n >= 1) min_factor[1] = -1;
        for (int p = 2; p * p <= n; p++) {
            if (min_factor[p] != p) continue;
            for (int i = p * p; i <= n; i += p) {
                if (min_factor[i] != i) continue;
                min_factor[i] = p;
            }
        }
    }

    bool is_prime(int x) {
        assert(x <= n);
        return min_factor[x] == x;
    }

    std::map<int, int> prime_factor(int x) {
        assert(x <= n);
        std::map<int, int> pf;
        while (x > 1) {
            pf[min_factor[x]]++;
            x /= min_factor[x];
        }
        return pf;
    }
};

#line 2 "math/osak.hpp"

struct Osak {
    int n;
    std::vector<int> min_factor;

    Osak(int n) : n(n), min_factor(n + 1) {
        std::iota(min_factor.begin(), min_factor.end(), 0);
        if (n >= 0) min_factor[0] = -1;
        if (n >= 1) min_factor[1] = -1;
        for (int p = 2; p * p <= n; p++) {
            if (min_factor[p] != p) continue;
            for (int i = p * p; i <= n; i += p) {
                if (min_factor[i] != i) continue;
                min_factor[i] = p;
            }
        }
    }

    bool is_prime(int x) {
        assert(x <= n);
        return min_factor[x] == x;
    }

    std::map<int, int> prime_factor(int x) {
        assert(x <= n);
        std::map<int, int> pf;
        while (x > 1) {
            pf[min_factor[x]]++;
            x /= min_factor[x];
        }
        return pf;
    }
};

Back to top page