competitive-programming-library
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ageprocpp/competitive-programming-library
math/CountPrime.hpp
- View this file on GitHub
- Last update: 2023-06-25 16:21:20+09:00
- Include:
#include "math/CountPrime.hpp"
Depends on
Verified with
Code
#pragma once
#include "../basic/template.hpp"
lint count_prime(lint x) {
static constexpr int table[] = {
1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7, 7, 7,
8, 8, 9, 10, 10, 11, 11, 11, 12, 12, 12, 13, 14, 14, 14, 15, 15, 16,
17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 22, 23, 23, 24,
25, 25, 26, 26, 26, 26, 26, 26, 26, 27, 27, 28, 28, 28, 29, 30, 30, 30,
30, 30, 31, 32, 32, 32, 33, 33, 33, 34, 34, 35, 36, 36, 37, 37, 37, 38,
39, 39, 39, 39, 39, 40, 41, 41, 42, 43, 43, 43, 43, 43, 43, 44, 44, 44,
44, 44, 45, 46, 46, 47, 48, 48, 49, 49, 49, 50, 51, 51, 51, 52, 52, 53,
53, 53, 54, 54, 54, 55, 55, 55, 56, 57, 57, 57, 58, 58, 59, 60, 60, 60,
61, 61, 62, 62, 62, 63, 63, 63, 63, 64, 64, 65, 66, 66, 67, 67, 67, 68,
68, 68, 68, 69, 69, 69, 70, 70, 70, 70, 70, 71, 72, 72, 73, 73, 73, 74,
75, 75, 75, 76, 76, 76, 77, 77, 78, 79, 79, 80, 80, 80, 81, 82, 82, 82,
83, 83, 84, 85, 85, 85, 86, 86, 86, 86, 86, 87, 88, 88, 88, 88, 88, 89,
90, 90, 91, 92, 92, 93, 93, 93, 94, 94, 94, 94, 95, 95, 96, 97, 97, 98,
98, 98, 98, 98, 98, 99, 100, 100, 100, 101, 101, 102, 103, 103, 103, 104, 104, 105,
105, 105, 106, 106, 106, 106, 106, 106, 107, 108, 108, 109, 110, 110, 111, 111, 111, 111,
112, 112, 112, 113, 113, 114, 114, 114, 115, 116, 116, 117, 117, 117, 118, 119, 119, 119,
120, 120, 120, 120, 120, 121, 122, 122, 123, 123, 123, 124, 125, 125, 125, 126, 126, 127,
128, 128, 129, 130, 130, 130, 130, 130, 131, 132, 132, 132, 132, 132, 133, 134, 134, 135,
135, 135, 136, 136, 136, 137, 138, 138, 138, 139, 139, 139, 140, 140, 141, 141, 141, 142,
142, 142, 143, 144, 144, 144, 145, 145, 146, 147, 147, 147, 148, 148, 149, 149, 149, 150,
150, 150, 150, 151, 151, 152, 153, 153, 153, 154, 154, 155, 155, 155, 155, 156, 156, 156,
157, 157, 158, 158, 158, 159, 160, 160, 161, 161, 161, 162, 162, 162, 162, 163, 163, 163,
164, 164, 165, 166, 166, 166, 166, 166, 167, 168, 168, 168, 169, 169, 170, 171, 171, 172,
173, 173, 173, 173, 173, 174, 175, 175, 175, 175, 175, 176, 177, 177, 178, 179, 179, 180,
180, 180, 180, 181, 181, 181, 182, 182, 183, 184, 184, 185, 185, 185, 186, 186, 186, 187,
188, 188, 188, 189, 189, 190, 190, 190, 190, 191, 191, 192, 192, 192, 193, 193, 193, 193,
194, 194, 195, 196, 196, 197, 198, 198, 199, 199, 199, 199, 200, 200, 200, 201, 201, 202,
202, 202, 203, 203, 203, 204, 204, 204, 205, 206, 206, 206, 207, 207, 207, 208, 208, 209,
210, 210, 211, 211, 211, 212, 213, 213, 213, 214, 214, 215, 216, 216, 217, 218, 218, 218,
218, 218, 219, 220, 220, 220, 220, 220, 221, 222, 222, 222, 223, 223, 224, 224, 224, 225,
226, 226, 226, 227, 227, 228, 229, 229, 230, 230, 230, 231, 231, 231, 232, 232, 232, 232,
233, 233, 234, 235, 235, 235, 236, 236, 236, 236, 236, 237, 237, 237, 237, 238, 238, 239,
240, 240, 241, 242, 242, 243, 243, 243, 243, 244, 244, 244, 244, 244, 245, 245, 245, 246,
247, 247, 248, 248, 248, 248, 249, 249, 249, 250, 250, 250, 251, 251, 252, 253, 253, 254,
254, 254, 255, 256, 256, 256, 257, 257, 258, 258, 258, 259, 260, 260, 260, 260, 260, 261,
262, 262, 262, 262, 262, 263, 264, 264, 265, 266, 266, 267, 267, 267, 268, 269, 269, 269,
270, 270, 271, 272, 272, 273, 273, 273, 274, 274, 274, 275, 276, 276, 276, 277, 277, 277,
278, 278, 278, 279, 279, 280, 280, 280, 281, 281, 281, 281, 282, 282, 283, 284, 284, 285,
286, 286, 287, 287, 287, 287, 288, 288, 288, 289, 289, 290, 290, 290, 290, 291, 291, 292,
292, 292, 293, 294, 294, 294, 295, 295, 295, 296, 296, 297, 298, 298, 299, 299, 299, 300,
300, 300, 300, 301, 301, 302, 303, 303, 304, 305, 305, 305, 305, 305, 306, 307, 307, 307,
307, 307, 308, 309, 309, 310, 311, 311, 312, 312, 312, 313, 314, 314, 314, 314, 314, 315,
316, 316, 317, 317, 317, 318, 318, 318, 318, 319, 319, 319, 320, 320, 321, 322, 322, 322,
323, 323, 324, 324, 324, 325, 325, 325, 325, 326, 326, 327, 327, 327, 328, 329, 329, 330,
330, 330, 330, 331, 331, 331, 332, 332, 333, 333, 333, 334, 335, 335, 336, 336, 336, 337,
338, 338, 338, 339, 339, 339, 340, 340, 341, 341, 341, 342, 342, 342, 343, 344, 344, 344,
345, 345, 345, 346, 346, 347, 348, 348, 348, 348, 348, 349, 350, 350, 350, 350, 350, 351,
352, 352, 353, 354, 354, 355, 355, 355, 356, 357, 357, 357, 358, 358, 359, 360, 360, 360,
360, 360, 361, 361, 361, 362, 363, 363, 363, 364, 364, 365, 366, 366, 366, 367, 367, 368,
368, 368, 369, 369, 369, 369, 370, 370, 371, 372, 372, 373, 374, 374, 374, 374, 374, 374,
375, 375, 375, 376, 376, 377, 377, 377, 378, 379, 379, 380, 380, 380, 381, 382, 382, 382,
382, 382, 382, 383, 383, 384, 385, 385, 386, 386, 386, 386, 387, 387, 387, 388, 388, 389,
390, 390, 391, 392, 392, 392, 392, 392, 393, 394, 394, 394, 394, 394, 395, 395, 395, 396,
397, 397, 398, 398, 398, 399, 400, 400, 400, 401, 401, 402, 403, 403, 404, 404, 404, 405,
405, 405, 406, 407, 407, 407, 408, 408, 409, 410, 410, 410, 410, 410, 411, 411, 411, 412,
412, 412, 412, 413, 413, 413, 414, 414, 415, 416, 416, 417, 417, 417, 417, 418, 418, 418,
419, 419, 420, 420, 420, 421, 422, 422, 423, 423, 423, 424, 425, 425, 425, 426, 426, 426,
427, 427, 427, 428, 428, 429, 429, 429, 430, 431, 431, 431, 432, 432, 433, 434, 434, 435,
436, 436, 436, 436, 436, 437, 437, 437, 437, 437, 437, 438, 439, 439, 440, 441, 441, 441,
441, 441, 442, 443, 443, 443, 444, 444, 445, 446, 446, 447, 447, 447, 448, 448, 448, 449,
450, 450, 450, 450, 450, 451, 452, 452, 452, 453, 453, 454, 454, 454, 454, 454, 454, 454,
455, 455, 456, 457, 457, 458, 459, 459, 460, 460, 460, 460, 461, 461, 461, 462, 462, 463,
463, 463, 464, 465, 465, 466, 466, 466, 467, 468, 468, 468, 469, 469, 469, 470, 470, 471,
472, 472, 473, 473, 473, 474, 475, 475, 475, 476, 476, 477, 478, 478, 479, 479, 479, 479,
479, 479, 480};
int b_ = std::sqrt(x) + 1, b = 0;
int c_ = std::cbrt(x) + 1, c = 0;
std::vector<bool> vec(c_ * c_ + 1, true);
std::vector<int> primes = {-1};
for (int i = 2; i <= c_ * c_; i++) {
if (vec[i]) {
primes.emplace_back(i);
if (i < b_) {
b++;
if (i < c_) c++;
}
for (int j = i << 1; j < vec.size(); j += i) vec[j] = false;
}
}
lint now = c, cnt = 0, sum = 0;
for (int i = primes.size() - 1; i > 0; i--) {
sum += cnt;
bool f = false;
while (lint(primes[i]) * primes[now + 1] <= x) {
cnt++, sum++, now++;
if (now == b) {
sum += lint(i - 1) * cnt;
f = true;
break;
}
}
if (f) break;
}
auto phi = lambda_fix([&](auto self, lint u, int v) -> lint {
if (u <= primes[v]) return 1;
if (v < 5) {
int cnt = 0;
for (int i = 1; i <= u; i++) {
bool f = true;
REP(j, v) if (i % primes[j] == 0) f = false;
if (f) cnt++;
}
return cnt;
}
if (v == 5) {
return 480 * (u / 2310) + table[(u % 2310 - 1) >> 1];
}
return self(self, u, v - 1) - self(self, u / primes[v], v - 1);
});
return phi(x, c) + lint(b + c - 2) * (b - c + 1) / 2 - sum;
}#line 2 "basic/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#ifndef __clang__
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)
#define all(V) V.begin(), V.end()
using i128 = __int128_t;
using u128 = __uint128_t;
using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;
using IP = std::pair<int, int>;
using LP = std::pair<lint, lint>;
constexpr int INF = INT_MAX / 2;
constexpr lint LINF = LLONG_MAX / 2;
constexpr double eps = DBL_EPSILON * 10;
constexpr double PI = 3.141592653589793238462643383279;
template <class T>
class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
int popcount(uint x) {
#if __cplusplus >= 202002L
return std::popcount(x);
#else
#ifndef __clang__
return __builtin_popcount(x);
#endif
#endif
x = (x & 0x55555555) + (x >> 1 & 0x55555555);
x = (x & 0x33333333) + (x >> 2 & 0x33333333);
x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff);
}
template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
return [f = std::forward<F>(f)](auto&&... args) {
return f(f, std::forward<decltype(args)>(args)...);
};
}
template <class T>
constexpr std::vector<T> make_vec(size_t n) {
return std::vector<T>(n);
}
template <class T, class... Args>
constexpr auto make_vec(size_t n, Args&&... args) {
return std::vector<decltype(make_vec<T>(args...))>(n, make_vec<T>(std::forward<Args>(args)...));
}
template <class T, class U, class Stream>
Stream& operator>>(Stream& ist, std::pair<T, U>& x) {
return ist >> x.first >> x.second;
}
template <class T, class U, class Stream>
Stream& operator<<(Stream& ost, const std::pair<T, U>& x) {
return ost << x.first << " " << x.second;
}
template <class Container,
std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr>
auto operator>>(std::istream& ist, Container& cont)
-> decltype(typename Container::iterator(), std::cin)& {
Container tmp;
while (true) {
typename Container::value_type t;
ist >> t;
tmp.emplace_back(t);
if (getchar() == '\n') break;
}
cont = Container(std::move(tmp));
return ist;
}
template <class Container, class Stream,
std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr>
auto operator<<(Stream& ost, const Container& cont)
-> decltype(typename Container::iterator(), ost)& {
for (auto it = cont.begin(); it != cont.end(); it++) {
if (it != cont.begin()) ost << ' ';
ost << *it;
}
return ost;
}
template <class Container>
auto sum(const Container& cont) -> decltype(typename Container::iterator(), 0LL) {
lint res = 0;
for (auto it = cont.begin(); it != cont.end(); it++) res += *it;
return res;
}
template <class T, class U>
constexpr inline bool chmax(T& lhs, const U& rhs) noexcept {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
constexpr inline bool chmin(T& lhs, const U& rhs) noexcept {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
constexpr inline lint gcd(lint a, lint b) noexcept {
while (b) {
lint c = a;
a = b;
b = c % b;
}
return a;
}
inline lint lcm(lint a, lint b) noexcept { return a / gcd(a, b) * b; }
constexpr bool isprime(lint n) noexcept {
if (n == 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
template <class T>
constexpr T mypow(T a, lint b) noexcept {
T res(1);
while (true) {
if (b & 1) res *= a;
b >>= 1;
if (!b) break;
a *= a;
}
return res;
}
constexpr lint modpow(lint a, lint b, lint m) noexcept {
a %= m;
lint res(1);
while (b) {
if (b & 1) res *= a, res %= m;
a *= a, a %= m, b >>= 1;
}
return res;
}
LP extGcd(lint a, lint b) noexcept {
if (b == 0) return {1, 0};
LP s = extGcd(b, a % b);
std::swap(s.first, s.second);
s.second -= a / b * s.first;
return s;
}
LP ChineseRem(const lint& b1, const lint& m1, const lint& b2, const lint& m2) noexcept {
auto p = extGcd(m1, m2);
lint g = gcd(m1, m2), l = m1 / g * m2;
lint tmp = (b2 - b1) / g * p.first % (m2 / g);
lint r = (b1 + m1 * tmp + l) % l;
return {r, l};
}
int LCS(const std::string& a, const std::string& b) {
auto dp = make_vec<int>(a.size() + 1, b.size() + 1);
rep(i, a.size()) {
rep(j, b.size()) {
chmax(dp[i + 1][j], dp[i][j]);
chmax(dp[i][j + 1], dp[i][j]);
if (a[i] == b[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
}
chmax(dp[i + 1][b.size()], dp[i][b.size()]);
}
rep(j, b.size()) chmax(dp[a.size()][j + 1], dp[a.size()][j]);
return dp[a.size()][b.size()];
}
template <class T, std::enable_if_t<std::is_convertible<int, T>::value, std::nullptr_t> = nullptr>
void compress(std::vector<T>& vec) {
auto tmp = vec;
std::sort(all(tmp));
tmp.erase(std::unique(all(tmp)), tmp.end());
for (T& i : vec) i = std::lower_bound(all(tmp), i) - tmp.begin();
}
template <class T>
void compress(T* l, T* r) {
std::vector<T> tmp(l, r);
std::sort(all(tmp));
tmp.erase(std::unique(all(tmp)), tmp.end());
for (auto i = l; i < r; i++) {
*i = std::lower_bound(all(tmp), *i) - tmp.begin();
}
}
template <class InputIter>
void compress(InputIter l, InputIter r) {
std::vector<typename InputIter::value_type> tmp(l, r);
std::sort(all(tmp));
tmp.erase(std::unique(all(tmp)), tmp.end());
for (auto i = l; i < r; i++) {
*i = std::lower_bound(all(tmp), *i) - tmp.begin();
}
}
template <class InputIter,
std::enable_if_t<std::is_same<typename InputIter::value_type, std::pair<IP, int>>::value,
std::nullptr_t> = nullptr>
void mo_sort(InputIter l, InputIter r, int N) {
const int M = std::max(1.0, std::sqrt(lint(N) * N / std::distance(l, r)));
std::sort(l, r, [M](const auto& lhs, const auto& rhs) {
if (lhs.first.first / M < rhs.first.first / M) return true;
if (lhs.first.first / M == rhs.first.first / M) return lhs.first.second < rhs.first.second;
return false;
});
int before = -1, cnt = 0;
bool f = false;
for (InputIter i = l; i != r; i++) {
if (before != i->first.first / M) {
if (f) std::reverse(i - cnt, i);
f ^= true, before = i->first.first / M, cnt = 1;
} else
cnt++;
}
if (f) std::reverse(r - cnt, r);
}
template <class T>
std::vector<T> xor_bases(const std::vector<T>& vec) {
std::vector<T> res;
for (T i : vec) {
for (T j : res) {
chmin(i, i ^ j);
}
if (i) res.emplace_back(i);
}
return res;
}
#line 3 "math/CountPrime.hpp"
lint count_prime(lint x) {
static constexpr int table[] = {
1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7, 7, 7,
8, 8, 9, 10, 10, 11, 11, 11, 12, 12, 12, 13, 14, 14, 14, 15, 15, 16,
17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 22, 23, 23, 24,
25, 25, 26, 26, 26, 26, 26, 26, 26, 27, 27, 28, 28, 28, 29, 30, 30, 30,
30, 30, 31, 32, 32, 32, 33, 33, 33, 34, 34, 35, 36, 36, 37, 37, 37, 38,
39, 39, 39, 39, 39, 40, 41, 41, 42, 43, 43, 43, 43, 43, 43, 44, 44, 44,
44, 44, 45, 46, 46, 47, 48, 48, 49, 49, 49, 50, 51, 51, 51, 52, 52, 53,
53, 53, 54, 54, 54, 55, 55, 55, 56, 57, 57, 57, 58, 58, 59, 60, 60, 60,
61, 61, 62, 62, 62, 63, 63, 63, 63, 64, 64, 65, 66, 66, 67, 67, 67, 68,
68, 68, 68, 69, 69, 69, 70, 70, 70, 70, 70, 71, 72, 72, 73, 73, 73, 74,
75, 75, 75, 76, 76, 76, 77, 77, 78, 79, 79, 80, 80, 80, 81, 82, 82, 82,
83, 83, 84, 85, 85, 85, 86, 86, 86, 86, 86, 87, 88, 88, 88, 88, 88, 89,
90, 90, 91, 92, 92, 93, 93, 93, 94, 94, 94, 94, 95, 95, 96, 97, 97, 98,
98, 98, 98, 98, 98, 99, 100, 100, 100, 101, 101, 102, 103, 103, 103, 104, 104, 105,
105, 105, 106, 106, 106, 106, 106, 106, 107, 108, 108, 109, 110, 110, 111, 111, 111, 111,
112, 112, 112, 113, 113, 114, 114, 114, 115, 116, 116, 117, 117, 117, 118, 119, 119, 119,
120, 120, 120, 120, 120, 121, 122, 122, 123, 123, 123, 124, 125, 125, 125, 126, 126, 127,
128, 128, 129, 130, 130, 130, 130, 130, 131, 132, 132, 132, 132, 132, 133, 134, 134, 135,
135, 135, 136, 136, 136, 137, 138, 138, 138, 139, 139, 139, 140, 140, 141, 141, 141, 142,
142, 142, 143, 144, 144, 144, 145, 145, 146, 147, 147, 147, 148, 148, 149, 149, 149, 150,
150, 150, 150, 151, 151, 152, 153, 153, 153, 154, 154, 155, 155, 155, 155, 156, 156, 156,
157, 157, 158, 158, 158, 159, 160, 160, 161, 161, 161, 162, 162, 162, 162, 163, 163, 163,
164, 164, 165, 166, 166, 166, 166, 166, 167, 168, 168, 168, 169, 169, 170, 171, 171, 172,
173, 173, 173, 173, 173, 174, 175, 175, 175, 175, 175, 176, 177, 177, 178, 179, 179, 180,
180, 180, 180, 181, 181, 181, 182, 182, 183, 184, 184, 185, 185, 185, 186, 186, 186, 187,
188, 188, 188, 189, 189, 190, 190, 190, 190, 191, 191, 192, 192, 192, 193, 193, 193, 193,
194, 194, 195, 196, 196, 197, 198, 198, 199, 199, 199, 199, 200, 200, 200, 201, 201, 202,
202, 202, 203, 203, 203, 204, 204, 204, 205, 206, 206, 206, 207, 207, 207, 208, 208, 209,
210, 210, 211, 211, 211, 212, 213, 213, 213, 214, 214, 215, 216, 216, 217, 218, 218, 218,
218, 218, 219, 220, 220, 220, 220, 220, 221, 222, 222, 222, 223, 223, 224, 224, 224, 225,
226, 226, 226, 227, 227, 228, 229, 229, 230, 230, 230, 231, 231, 231, 232, 232, 232, 232,
233, 233, 234, 235, 235, 235, 236, 236, 236, 236, 236, 237, 237, 237, 237, 238, 238, 239,
240, 240, 241, 242, 242, 243, 243, 243, 243, 244, 244, 244, 244, 244, 245, 245, 245, 246,
247, 247, 248, 248, 248, 248, 249, 249, 249, 250, 250, 250, 251, 251, 252, 253, 253, 254,
254, 254, 255, 256, 256, 256, 257, 257, 258, 258, 258, 259, 260, 260, 260, 260, 260, 261,
262, 262, 262, 262, 262, 263, 264, 264, 265, 266, 266, 267, 267, 267, 268, 269, 269, 269,
270, 270, 271, 272, 272, 273, 273, 273, 274, 274, 274, 275, 276, 276, 276, 277, 277, 277,
278, 278, 278, 279, 279, 280, 280, 280, 281, 281, 281, 281, 282, 282, 283, 284, 284, 285,
286, 286, 287, 287, 287, 287, 288, 288, 288, 289, 289, 290, 290, 290, 290, 291, 291, 292,
292, 292, 293, 294, 294, 294, 295, 295, 295, 296, 296, 297, 298, 298, 299, 299, 299, 300,
300, 300, 300, 301, 301, 302, 303, 303, 304, 305, 305, 305, 305, 305, 306, 307, 307, 307,
307, 307, 308, 309, 309, 310, 311, 311, 312, 312, 312, 313, 314, 314, 314, 314, 314, 315,
316, 316, 317, 317, 317, 318, 318, 318, 318, 319, 319, 319, 320, 320, 321, 322, 322, 322,
323, 323, 324, 324, 324, 325, 325, 325, 325, 326, 326, 327, 327, 327, 328, 329, 329, 330,
330, 330, 330, 331, 331, 331, 332, 332, 333, 333, 333, 334, 335, 335, 336, 336, 336, 337,
338, 338, 338, 339, 339, 339, 340, 340, 341, 341, 341, 342, 342, 342, 343, 344, 344, 344,
345, 345, 345, 346, 346, 347, 348, 348, 348, 348, 348, 349, 350, 350, 350, 350, 350, 351,
352, 352, 353, 354, 354, 355, 355, 355, 356, 357, 357, 357, 358, 358, 359, 360, 360, 360,
360, 360, 361, 361, 361, 362, 363, 363, 363, 364, 364, 365, 366, 366, 366, 367, 367, 368,
368, 368, 369, 369, 369, 369, 370, 370, 371, 372, 372, 373, 374, 374, 374, 374, 374, 374,
375, 375, 375, 376, 376, 377, 377, 377, 378, 379, 379, 380, 380, 380, 381, 382, 382, 382,
382, 382, 382, 383, 383, 384, 385, 385, 386, 386, 386, 386, 387, 387, 387, 388, 388, 389,
390, 390, 391, 392, 392, 392, 392, 392, 393, 394, 394, 394, 394, 394, 395, 395, 395, 396,
397, 397, 398, 398, 398, 399, 400, 400, 400, 401, 401, 402, 403, 403, 404, 404, 404, 405,
405, 405, 406, 407, 407, 407, 408, 408, 409, 410, 410, 410, 410, 410, 411, 411, 411, 412,
412, 412, 412, 413, 413, 413, 414, 414, 415, 416, 416, 417, 417, 417, 417, 418, 418, 418,
419, 419, 420, 420, 420, 421, 422, 422, 423, 423, 423, 424, 425, 425, 425, 426, 426, 426,
427, 427, 427, 428, 428, 429, 429, 429, 430, 431, 431, 431, 432, 432, 433, 434, 434, 435,
436, 436, 436, 436, 436, 437, 437, 437, 437, 437, 437, 438, 439, 439, 440, 441, 441, 441,
441, 441, 442, 443, 443, 443, 444, 444, 445, 446, 446, 447, 447, 447, 448, 448, 448, 449,
450, 450, 450, 450, 450, 451, 452, 452, 452, 453, 453, 454, 454, 454, 454, 454, 454, 454,
455, 455, 456, 457, 457, 458, 459, 459, 460, 460, 460, 460, 461, 461, 461, 462, 462, 463,
463, 463, 464, 465, 465, 466, 466, 466, 467, 468, 468, 468, 469, 469, 469, 470, 470, 471,
472, 472, 473, 473, 473, 474, 475, 475, 475, 476, 476, 477, 478, 478, 479, 479, 479, 479,
479, 479, 480};
int b_ = std::sqrt(x) + 1, b = 0;
int c_ = std::cbrt(x) + 1, c = 0;
std::vector<bool> vec(c_ * c_ + 1, true);
std::vector<int> primes = {-1};
for (int i = 2; i <= c_ * c_; i++) {
if (vec[i]) {
primes.emplace_back(i);
if (i < b_) {
b++;
if (i < c_) c++;
}
for (int j = i << 1; j < vec.size(); j += i) vec[j] = false;
}
}
lint now = c, cnt = 0, sum = 0;
for (int i = primes.size() - 1; i > 0; i--) {
sum += cnt;
bool f = false;
while (lint(primes[i]) * primes[now + 1] <= x) {
cnt++, sum++, now++;
if (now == b) {
sum += lint(i - 1) * cnt;
f = true;
break;
}
}
if (f) break;
}
auto phi = lambda_fix([&](auto self, lint u, int v) -> lint {
if (u <= primes[v]) return 1;
if (v < 5) {
int cnt = 0;
for (int i = 1; i <= u; i++) {
bool f = true;
REP(j, v) if (i % primes[j] == 0) f = false;
if (f) cnt++;
}
return cnt;
}
if (v == 5) {
return 480 * (u / 2310) + table[(u % 2310 - 1) >> 1];
}
return self(self, u, v - 1) - self(self, u / primes[v], v - 1);
});
return phi(x, c) + lint(b + c - 2) * (b - c + 1) / 2 - sum;
}