math/primefactor2.cpp

• View this file on GitHub
• Last update: 2021-06-21 15:24:20+09:00

Code

using uint = uint32_t;

template<typename T>
struct ExactDiv {
    T t, i, val;
    ExactDiv() {}
    ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) , val(n) {};
    T mul_inv(T n) {
        T x = n;
        for (int i = 0; i < 5; ++i) x *= 2 - n * x;
        return x;
    }
    bool divide(T n) const {
        if(val == 2) return !(n & 1);
        return n * this->i <= this->t;
    }
};

vector<ExactDiv<uint>> get_prime(int n){
    if(n <= 1) return vector<ExactDiv<uint>>();
    vector<bool> is_prime(n+1, true);
    vector<ExactDiv<uint>> prime;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if(is_prime[i]) prime.emplace_back(i);
        for (auto &&j : prime){
            if(i*j.val > n) break;
            is_prime[i*j.val] = false;
            if(j.divide(i)) break;
        }
    }
    return prime;
}
const auto primes = get_prime(32000);

template<class T>
vector<T> prime_factor(T n){
    vector<T> res;
    for (auto &&i : primes) {
        while (i.divides(n)){
            res.emplace_back(i.val);
            n /= i.val;
        }
    }
    if(n != 1) res.emplace_back(n);
    return res;
}

#line 1 "math/primefactor2.cpp"
using uint = uint32_t;

template<typename T>
struct ExactDiv {
    T t, i, val;
    ExactDiv() {}
    ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) , val(n) {};
    T mul_inv(T n) {
        T x = n;
        for (int i = 0; i < 5; ++i) x *= 2 - n * x;
        return x;
    }
    bool divide(T n) const {
        if(val == 2) return !(n & 1);
        return n * this->i <= this->t;
    }
};

vector<ExactDiv<uint>> get_prime(int n){
    if(n <= 1) return vector<ExactDiv<uint>>();
    vector<bool> is_prime(n+1, true);
    vector<ExactDiv<uint>> prime;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if(is_prime[i]) prime.emplace_back(i);
        for (auto &&j : prime){
            if(i*j.val > n) break;
            is_prime[i*j.val] = false;
            if(j.divide(i)) break;
        }
    }
    return prime;
}
const auto primes = get_prime(32000);

template<class T>
vector<T> prime_factor(T n){
    vector<T> res;
    for (auto &&i : primes) {
        while (i.divides(n)){
            res.emplace_back(i.val);
            n /= i.val;
        }
    }
    if(n != 1) res.emplace_back(n);
    return res;
}

Back to top page