verify/yosupo-counting-primes.test.cpp

• View this file on GitHub
• Last update: 2026-06-03 21:23:32+09:00
• Problem: https://judge.yosupo.jp/problem/counting_primes

Depends on

• $m$ で割った余りごとの $N$ 以下の素数の個数の列挙 (math/multiplicative-function/prime-counting-modulo.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/counting_primes

#include <iostream>

#include "../math/multiplicative-function/prime-counting-modulo.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long N;
    std::cin >> N;
    std::cout << prime_counting_modulo(N, 1)[0] << '\n';
    return 0;
}

#line 1 "verify/yosupo-counting-primes.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/counting_primes

#include <iostream>

#line 1 "math/multiplicative-function/prime-counting-modulo.hpp"



// N 以下の素数を、m で割った余りごとに数える。
// Lucy DP のテーブルを余りごとに持ち、素数 x によるふるいを同時に行う。
// N は非負、m は正を仮定する。
// 戻り値のテーブルの 1 つ目の添字は m で割った余りである。
// 計算量 O(m N^{3/4} / log N)、空間 O(m sqrt(N))。

#include <cassert>
#include <utility>
#include <vector>

namespace prime_counting_modulo_internal {
inline long long integer_sqrt(long long n) {
    assert(n >= 0);
    long long ok = 0, ng = 1;
    while (ng <= n / ng) {
        ng <<= 1;
    }
    while (ng - ok > 1) {
        const long long mid = ok + (ng - ok) / 2;
        if (mid <= n / mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

inline long long count_residue_2_to_n(long long n, long long m, long long r) {
    assert(n >= 0);
    assert(m > 0);
    assert(0 <= r && r < m);
    long long res = 0;
    if (r <= n) {
        res = (n - r) / m + 1;
    }
    if (r == 0) {
        --res;
    }
    if (n >= 1 && r == 1 % m) {
        --res;
    }
    return res;
}

inline void add_mod(long long &x, long long a, long long m) {
    assert(0 <= x && x < m);
    assert(0 <= a && a < m);
    if (a == 0) {
        return;
    }
    if (x >= m - a) {
        x -= m - a;
    } else {
        x += a;
    }
}
} // namespace prime_counting_modulo_internal

inline std::pair<std::vector<long long>, std::vector<std::vector<long long>>>
prime_counting_modulo_table(long long N, long long m) {
    assert(N >= 0);
    assert(m > 0);
    using i64 = long long;
    std::vector<i64> ns{0};
    for (i64 i = N; i > 0;) {
        ns.push_back(i);
        const i64 q = N / i;
        if (q == N) {
            break;
        }
        i = N / (q + 1);
    }
    const i64 sq = prime_counting_modulo_internal::integer_sqrt(N);
    const i64 nsz = static_cast<i64>(ns.size());
    std::vector<std::vector<i64>> h(m, std::vector<i64>(nsz));
    for (i64 r = 0; r < m; ++r) {
        for (i64 i = 0; i < nsz; ++i) {
            h[r][i] = prime_counting_modulo_internal::count_residue_2_to_n(
                ns[i], m, r);
        }
    }
    for (i64 x = 2; x <= sq; ++x) {
        const i64 x_mod = x % m;
        const i64 x_idx = nsz - x;
        const i64 prev_idx = nsz - x + 1;
        if (h[x_mod][x_idx] == h[x_mod][prev_idx]) {
            continue;
        }
        const i64 x2 = x * x;
        for (i64 i = 1; i < nsz && ns[i] >= x2; ++i) {
            const i64 n = ns[i];
            const i64 q = n / x;
            const i64 q_idx = i <= sq / x ? i * x : nsz - q;
            i64 to = 0;
            for (i64 r = 0; r < m; ++r) {
                h[to][i] -= h[r][q_idx] - h[r][prev_idx];
                prime_counting_modulo_internal::add_mod(to, x_mod, m);
            }
        }
    }
    return {ns, h};
}

inline std::vector<long long> prime_counting_modulo(long long N, long long m) {
    assert(N >= 0);
    assert(m > 0);
    std::vector<long long> res(m);
    if (N == 0) {
        return res;
    }
    const auto table = prime_counting_modulo_table(N, m).second;
    for (long long r = 0; r < m; ++r) {
        res[r] = table[r][1];
    }
    return res;
}

template <class T>
std::vector<std::vector<T>>
prime_counting_modulo_mf_prefix_sum_table(long long N, long long m) {
    assert(N >= 0);
    assert(m > 0);
    std::vector<std::vector<T>> res(m);
    if (N == 0) {
        return res;
    }
    const auto table = prime_counting_modulo_table(N, m).second;
    for (long long r = 0; r < m; ++r) {
        res[r].resize(table[r].size());
        for (long long i = 0; i < static_cast<long long>(table[r].size());
             ++i) {
            res[r][i] = static_cast<T>(table[r][i]);
        }
    }
    return res;
}


#line 6 "verify/yosupo-counting-primes.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long N;
    std::cin >> N;
    std::cout << prime_counting_modulo(N, 1)[0] << '\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	Grothendieck_prime_00	AC	2 ms	4 MB
g++	boundaryA_00	AC	1551 ms	24 MB
g++	boundaryA_01	AC	1051 ms	18 MB
g++	boundaryA_02	AC	1088 ms	18 MB
g++	boundaryB_00	AC	1558 ms	23 MB
g++	boundaryB_01	AC	1049 ms	18 MB
g++	boundaryB_02	AC	1092 ms	18 MB
g++	example_00	AC	2 ms	3 MB
g++	example_01	AC	2 ms	3 MB
g++	max_00	AC	1594 ms	23 MB
g++	max_01	AC	1592 ms	23 MB
g++	max_02	AC	1587 ms	24 MB
g++	max_03	AC	1599 ms	24 MB
g++	max_04	AC	1593 ms	24 MB
g++	random_00	AC	1551 ms	24 MB
g++	random_01	AC	1068 ms	18 MB
g++	random_02	AC	1086 ms	18 MB
g++	random_03	AC	921 ms	16 MB
g++	random_04	AC	531 ms	12 MB
g++	small_00	AC	4 ms	4 MB
g++	small_01	AC	3 ms	4 MB
g++	small_02	AC	3 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_prime_00	AC	2 ms	4 MB
g++	small_prime_01	AC	2 ms	3 MB
g++	very_small_00	AC	2 ms	4 MB
g++	very_small_01	AC	2 ms	4 MB
g++	very_small_02	AC	2 ms	4 MB
g++	very_small_03	AC	2 ms	4 MB
g++	very_small_04	AC	2 ms	4 MB
clang++	Grothendieck_prime_00	AC	2 ms	4 MB
clang++	boundaryA_00	AC	1983 ms	23 MB
clang++	boundaryA_01	AC	1336 ms	18 MB
clang++	boundaryA_02	AC	1379 ms	18 MB
clang++	boundaryB_00	AC	1985 ms	24 MB
clang++	boundaryB_01	AC	1346 ms	18 MB
clang++	boundaryB_02	AC	1381 ms	18 MB
clang++	example_00	AC	2 ms	3 MB
clang++	example_01	AC	2 ms	3 MB
clang++	max_00	AC	2025 ms	23 MB
clang++	max_01	AC	2014 ms	23 MB
clang++	max_02	AC	2006 ms	23 MB
clang++	max_03	AC	2018 ms	24 MB
clang++	max_04	AC	2009 ms	23 MB
clang++	random_00	AC	1985 ms	24 MB
clang++	random_01	AC	1360 ms	18 MB
clang++	random_02	AC	1378 ms	18 MB
clang++	random_03	AC	1135 ms	16 MB
clang++	random_04	AC	674 ms	12 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	3 ms	3 MB
clang++	small_03	AC	5 ms	4 MB
clang++	small_04	AC	5 ms	4 MB
clang++	small_prime_00	AC	2 ms	3 MB
clang++	small_prime_01	AC	2 ms	3 MB
clang++	very_small_00	AC	2 ms	3 MB
clang++	very_small_01	AC	2 ms	4 MB
clang++	very_small_02	AC	2 ms	3 MB
clang++	very_small_03	AC	2 ms	3 MB
clang++	very_small_04	AC	2 ms	4 MB

Back to top page