test/yosupo/counting_primes.test.cpp

View this file on GitHub
Last update: 2024-01-08 17:31:43+09:00
Problem: https://judge.yosupo.jp/problem/counting_primes

Depends on

Prime Counting Function (math/number-theory/prime_count.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/counting_primes"

#include "../../math/number-theory/prime_count.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    long long N;
    cin >> N;
    cout << prime_count(N) << endl;
}

#line 1 "test/yosupo/counting_primes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/counting_primes"

#line 2 "math/number-theory/prime_count.hpp"
#include <cmath>
#include <vector>

long long prime_count(long long n) {
    int s = (int)std::sqrt(n);
    std::vector<long long> small(n / s + 1), large(s + 1);
    for (int i = 1; i <= n / s; ++i) small[i] = i - 1;
    for (int i = 1; i <= s; ++i) large[i] = n / i - 1;
    for (long long i = 2; i <= s; ++i) {
        if (small[i - 1] == small[i]) continue;  // i is not prime
        long long pi = small[i - 1];
        for (long long j = 1; j <= s && n / j >= i * i; ++j) {
            long long x = i * j <= s ? large[i * j] : small[n / (i * j)];
            if (j <= s) {
                large[j] -= x - pi;
            }
            if (n / j <= n / s) {
                small[n / j] -= x - pi;
            }
        }
        for (long long j = n / s - 1; j >= i * i; --j) {
            small[j] -= small[j / i] - pi;
        }
    }
    return large[1];
}
#line 4 "test/yosupo/counting_primes.test.cpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    long long N;
    cin >> N;
    cout << prime_count(N) << endl;
}