EratosthenesSieve
(src/math/eratosthenes_sieve.hpp)

• View this file on GitHub
• Last update: 2025-02-22 22:56:16+09:00
• Include: #include "src/math/eratosthenes_sieve.hpp"

EratosthenesSieve

EratosthenesSieve sieve(int N)

$N$ 以下の正の整数に対してエラトステネスの篩を行います．

メンバ変数

(1) vector<int> sieve.primes
(2) vector<int> sieve.min_factor
(3) vector<int> sieve.moebius
(4) vector<int> sieve.euler

• (1): $N$ 以下の素数が昇順に格納されています．
• (2): sieve.min_factor[i] に $i$ の素因数の最小値が格納された，長さ $N + 1$ の配列です．
  便宜上 min_factor[0] = min_factor[1] = -1 としています．
  $i$ が素数であることと min_factor[i] = i であることは同値です．
  
• (3): sieve.moebius[i] に $\mu(i)$ が格納された，長さ $N + 1$ の配列です．
• (4): sieve.euler[i] に $\phi(i)$ が格納された，長さ $N + 1$ の配列です．

制約

• $1 \leq N$

計算量

• $O(N \log \log N)$

prime_factors

vector<pair<int, int>> prime_factors(int n)

正整数 $n$ を素因数分解します．

制約

• $1 \leq n \leq N$

計算量

• $O(\log{n})$

divisor

vector<int> divisor(int n)

正整数 $n$ の正の約数を昇順に返します．

制約

• $1 \leq n \leq N$

計算量

• $O(\log{n})$

Depends on

• template (src/template/template.hpp)

Required by

• gcd_convolution (src/convolution/gcd_convolution.hpp)
• lcm_convolution (src/convolution/lcm_convolution.hpp)
• Divisor/MultipleTransform (src/math/divisor_multiple_transform.hpp)

Verified with

• verify/aizu_online_judge/alds1/prime_numbers_2.test.cpp
• verify/library_checker/convolution/gcd_convolution.test.cpp
• verify/library_checker/convolution/lcm_convolution.test.cpp
• verify/unit_test/math/eratosthenes_sieve.test.cpp

Code

#pragma once
#include "../template/template.hpp"
struct EratosthenesSieve {
    vector<int> primes, min_factor, moebius, euler;
    EratosthenesSieve(const int N)
        : primes(), min_factor(N + 1), moebius(N + 1, 1), euler(N + 1), N(N) {
        assert(N >= 1);
        iota(min_factor.begin(), min_factor.end(), 0);
        min_factor[0] = min_factor[1] = -1;
        iota(euler.begin(), euler.end(), 0);
        for(int i = 2; i <= N; ++i) {
            if(min_factor[i] < i) continue;
            primes.emplace_back(i);
            moebius[i] = -1;
            euler[i] = euler[i] / i * (i - 1);
            for(int j = i * 2; j <= N; j += i) {
                if(min_factor[j] == j) min_factor[j] = i;
                if((j / i) % i == 0) moebius[j] = 0;
                else moebius[j] = -moebius[j];
                euler[j] = euler[j] / i * (i - 1);
            }
        }
    }
    vector<pair<int, int>> prime_factors(int n) const {
        assert(1 <= n and n <= N);
        vector<pair<int, int>> res;
        while(n > 1) {
            const int p = min_factor[n];
            int exp = 0;
            while(min_factor[n] == p) {
                n /= p;
                ++exp;
            }
            res.emplace_back(p, exp);
        }
        return res;
    }
    vector<int> divisor(const int n) const {
        assert(1 <= n and n <= n);
        vector<int> res({1});
        const auto pf = prime_factors(n);
        for(const auto& p : pf) {
            const int s = (int)res.size();
            for(int i = 0; i < s; ++i) {
                int v = 1;
                for(int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

   private:
    int N;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/eratosthenes_sieve.hpp"
struct EratosthenesSieve {
    vector<int> primes, min_factor, moebius, euler;
    EratosthenesSieve(const int N)
        : primes(), min_factor(N + 1), moebius(N + 1, 1), euler(N + 1), N(N) {
        assert(N >= 1);
        iota(min_factor.begin(), min_factor.end(), 0);
        min_factor[0] = min_factor[1] = -1;
        iota(euler.begin(), euler.end(), 0);
        for(int i = 2; i <= N; ++i) {
            if(min_factor[i] < i) continue;
            primes.emplace_back(i);
            moebius[i] = -1;
            euler[i] = euler[i] / i * (i - 1);
            for(int j = i * 2; j <= N; j += i) {
                if(min_factor[j] == j) min_factor[j] = i;
                if((j / i) % i == 0) moebius[j] = 0;
                else moebius[j] = -moebius[j];
                euler[j] = euler[j] / i * (i - 1);
            }
        }
    }
    vector<pair<int, int>> prime_factors(int n) const {
        assert(1 <= n and n <= N);
        vector<pair<int, int>> res;
        while(n > 1) {
            const int p = min_factor[n];
            int exp = 0;
            while(min_factor[n] == p) {
                n /= p;
                ++exp;
            }
            res.emplace_back(p, exp);
        }
        return res;
    }
    vector<int> divisor(const int n) const {
        assert(1 <= n and n <= n);
        vector<int> res({1});
        const auto pf = prime_factors(n);
        for(const auto& p : pf) {
            const int s = (int)res.size();
            for(int i = 0; i < s; ++i) {
                int v = 1;
                for(int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

   private:
    int N;
};

Back to top page