Sieve of Eratosthenes
(C++/math/primetable.hpp)

• View this file on GitHub
• Last update: 2024-03-29 03:01:20+09:00
• Include: #include "C++/math/primetable.hpp"

Required by

• 素数の個数 (C++/math/primecounter.hpp)
• テンプレート (C++/template.hpp)

Verified with

• test/aarray.test.cpp
• test/add.test.cpp
• test/add128.test.cpp
• test/extgcd.test.cpp
• test/fwtree.test.cpp
• test/m_add.test.cpp
• test/parsum.test.cpp
• test/pcounter.test.cpp
• test/s_rmq.test.cpp
• test/segtree.test.cpp
• test/sr_sum.test.cpp
• test/stable.test.cpp
• test/uf.test.cpp

Code

#pragma once

#include <vector>
namespace Heileden {
struct p_table {
    std::vector<int> SoE;
    p_table(const int n): SoE(n + 1, 1) {
        SoE[0] = SoE[1] = 0;
        for(int64_t i = 2; i <= n; ++i) {
            if(!SoE[i]) {
                continue;
            }
            for(int64_t j = i * i; j <= n; j += i) {
                SoE[j] = 0;
            }
        }
    }
    std::vector<int> get() {
        std::vector<int> p;
        for(size_t i = 2; i < SoE.size(); ++i) {
            if(SoE[i]) {
                p.emplace_back(i);
            }
        }
        return p;
    }
};
}

/**
 * @brief Sieve of Eratosthenes
 */

#line 2 "C++/math/primetable.hpp"

#include <vector>
namespace Heileden {
struct p_table {
    std::vector<int> SoE;
    p_table(const int n): SoE(n + 1, 1) {
        SoE[0] = SoE[1] = 0;
        for(int64_t i = 2; i <= n; ++i) {
            if(!SoE[i]) {
                continue;
            }
            for(int64_t j = i * i; j <= n; j += i) {
                SoE[j] = 0;
            }
        }
    }
    std::vector<int> get() {
        std::vector<int> p;
        for(size_t i = 2; i < SoE.size(); ++i) {
            if(SoE[i]) {
                p.emplace_back(i);
            }
        }
        return p;
    }
};
}

/**
 * @brief Sieve of Eratosthenes
 */

Back to top page