Math/Prime/Sieve.h

• View this file on GitHub
• Last update: 2022-12-14 02:22:04+08:00

Required by

• Math/NumberTheory/cnt_divisors.h

Verified with

• Math/tests/cnt_divisors_stress.test.cpp
• Math/tests/sieve.test.cpp

Code

// F is called for each prime
// Sieve (odd only + segmented) {{{
template<typename F>
void sieve(int MAX, F func) {

    const int S = sqrt(MAX + 0.5);
    vector<char> sieve(S + 1, true);
    vector<array<int, 2>> cp;
    for (int i = 3; i <= S; i += 2) {
        if (!sieve[i])
            continue;
        cp.push_back({i, (i * i - 1) / 2});
        for (int j = i * i; j <= S; j += 2 * i)
            sieve[j] = false;
    }
    func(2);
    vector<char> block(S);
    int high = (MAX - 1) / 2;
    for (int low = 0; low <= high; low += S) {
        fill(block.begin(), block.end(), true);
        for (auto &i : cp) {
            int p = i[0], idx = i[1];
            for (; idx < S; idx += p)
                block[idx] = false;
            i[1] = idx - S;
        }
        if (low == 0)
            block[0] = false;
        for (int i = 0; i < S && low + i <= high; i++)
            if (block[i]) {
                func((low + i) * 2 + 1);
            }
    };
}
// }}}

#line 1 "Math/Prime/Sieve.h"
// F is called for each prime
// Sieve (odd only + segmented) {{{
template<typename F>
void sieve(int MAX, F func) {

    const int S = sqrt(MAX + 0.5);
    vector<char> sieve(S + 1, true);
    vector<array<int, 2>> cp;
    for (int i = 3; i <= S; i += 2) {
        if (!sieve[i])
            continue;
        cp.push_back({i, (i * i - 1) / 2});
        for (int j = i * i; j <= S; j += 2 * i)
            sieve[j] = false;
    }
    func(2);
    vector<char> block(S);
    int high = (MAX - 1) / 2;
    for (int low = 0; low <= high; low += S) {
        fill(block.begin(), block.end(), true);
        for (auto &i : cp) {
            int p = i[0], idx = i[1];
            for (; idx < S; idx += p)
                block[idx] = false;
            i[1] = idx - S;
        }
        if (low == 0)
            block[0] = false;
        for (int i = 0; i < S && low + i <= high; i++)
            if (block[i]) {
                func((low + i) * 2 + 1);
            }
    };
}
// }}}

Back to top page