math/prime_table.hpp

• View this file on GitHub
• Last update: 2023-02-06 17:52:27+09:00
• Include: #include "math/prime_table.hpp"

Required by

• math/enumerate_primes.hpp

Verified with

• verify/aoj_alds1/aoj_alds1_1_c.test.cpp
• verify/lc_math/lc_enumerate_primes.test.cpp

Code

#pragma once

std::vector<bool> prime_table(int n) {
    std::vector<bool> res(n + 1, true);
    if (n >= 0) res[0] = false;
    if (n >= 1) res[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (!res[p]) continue;
        for (int i = p * p; i <= n; i += p) {
            res[i] = false;
        }
    }
    return res;
}

#line 2 "math/prime_table.hpp"

std::vector<bool> prime_table(int n) {
    std::vector<bool> res(n + 1, true);
    if (n >= 0) res[0] = false;
    if (n >= 1) res[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (!res[p]) continue;
        for (int i = p * p; i <= n; i += p) {
            res[i] = false;
        }
    }
    return res;
}

Back to top page