Eratosthenes Sieve
(math/eratosthenes_sieve.hpp)

• View this file on GitHub
• Last update: 2023-08-23 17:33:30+09:00
• Include: #include "math/eratosthenes_sieve.hpp"
• Link: https://37zigen.com/sieve-eratosthenes/

説明

$N$ 以下の素数を列挙する。 $O(N\log \log N)$

Required by

• Dirichlet Convolution (convolution/dirichlet_convolution.hpp)
• GCD Convolution (convolution/gcd_convolution.hpp)
• LCM Convolution (convolution/lcm_convolution.hpp)
• Dirichlet Series (math/DirichletSeries.hpp)
• Divisor Transform (Zeta / Möbius) (math/divisor_transform.hpp)
• Multiple Transform (Zeta / Möbius) (math/multiple_transform.hpp)

Verified with

• test/convolution/Gcd_Convolution.test.cpp
• test/convolution/Lcm_Convolution.test.cpp
• test/math/Enumerate_Primes.test.cpp
• test/math/Sum_of_Totient_Function.test.cpp
• test/math/eratosthenes_sieve.test.cpp

Code

#pragma once

#include <cassert>

#include <cstdint>

#include <vector>


/*
    reference: https://37zigen.com/sieve-eratosthenes/
*/

namespace ebi {

struct eratosthenes_sieve {
  private:
    using i64 = std::int_fast64_t;
    int n;
    std::vector<bool> table;

  public:
    eratosthenes_sieve(int _n) : n(_n), table(std::vector<bool>(n + 1, true)) {
        table[1] = false;
        for (i64 i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (i64 j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    std::vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        for (int i = 2; i <= m; i++) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace ebi

#line 2 "math/eratosthenes_sieve.hpp"

#include <cassert>

#include <cstdint>

#include <vector>


/*
    reference: https://37zigen.com/sieve-eratosthenes/
*/

namespace ebi {

struct eratosthenes_sieve {
  private:
    using i64 = std::int_fast64_t;
    int n;
    std::vector<bool> table;

  public:
    eratosthenes_sieve(int _n) : n(_n), table(std::vector<bool>(n + 1, true)) {
        table[1] = false;
        for (i64 i = 2; i * i <= n; i++) {
            if (!table[i]) continue;
            for (i64 j = i; i * j <= n; j++) {
                table[i * j] = false;
            }
        }
    }

    bool is_prime(int p) {
        return table[p];
    }

    std::vector<int> prime_table(int m = -1) {
        if (m < 0) m = n;
        std::vector<int> prime;
        for (int i = 2; i <= m; i++) {
            if (table[i]) prime.emplace_back(i);
        }
        return prime;
    }
};

}  // namespace ebi

Back to top page