sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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; }