简单学习 Meissel–Lehmer 算法 后可得（反正我没看懂，以下由 $AI$ 生成）：

1. 核心辅助函数 $\phi(x, a)$

定义 $\phi(x, a)$ 为不超过 $x$ 且不能被前 $a$ 个质数整除的正整数个数。它满足递推关系：

$$\phi(x, a) = \phi(x, a-1) - \phi\left(\left\lfloor \frac{x}{p_a} \right\rfloor, a-1\right)$$

其含义是：不被前 $a$ 个质数整除的数 = 不被前 $a-1$ 个质数整除的数 − 其中能被 $p_a$ 整除的数。

当 $p_a^2 > x$ 时，所有不超过 $x$ 且不含前 $a$ 个质因子的数只能是 1 或大于 $p_{a-1}$ 的质数，因此可直接计算为 $\pi(x) - a + 1$，无需继续递归。这是算法高效的关键剪枝。

2. Meissel-Lehmer 主公式

选取参数 $a = \pi(n^{1/3})$，则有：

$$\pi(n) = \phi(n, a) + a - 1 - \sum_{\substack{p_i > n^{1/3} \\ p_i^2 \le n}} \left( \pi\left(\left\lfloor \frac{n}{p_i} \right\rfloor\right) - \pi(p_i) + 1 \right)$$

公式推导逻辑：

• $\phi(n, a)$ 统计了所有不超过 $n$ 且最小质因子 $> p_a$ 的数（包括 1 和所有大质数）。
• 由于 $p_a \approx n^{1/3}$，这样的合数至多有两个质因子（因为三个 $> n^{1/3}$ 的质数之积已超过 $n$）。
• 因此 $\phi(n, a) - 1 + a$ 等于 $\pi(n)$ 加上所有形如 $p_i \cdot q$（其中 $p_i > n^{1/3}, q \ge p_i, p_i q \le n$）的合数个数。
• 求和项正是对这些“双大质因子合数”的精确扣除：对每个满足条件的 $p_i$，合法的 $q$ 的个数为 $\pi(n/p_i) - \pi(p_i) + 1$。

3. 复杂度控制原理

• 选择 $a = \pi(n^{1/3})$ 使得 $\phi(n, a)$ 的递归深度和状态数被限制在 $O(n^{2/3})$ 量级。
• 求和项中的 $p_i$ 范围为 $(n^{1/3}, \sqrt{n}]$，数量为 $O(n^{1/3}/\log n)$，且每次递归调用 $\pi(n/p_i)$ 的参数 $< n^{2/3}$，可通过预处理的小范围 $\pi$ 值或相同方法快速求解。
• 结合 $\phi$ 函数的平方剪枝和小范围记忆化，整体时间复杂度稳定为 $O(n^{2/3})$，空间复杂度为 $O(n^{1/3})$ 级别。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=10000010,M=1200010;
int f[M+5][65],p[N/10],g[N],cnt;
bool ip[N];
inline void init(){
	for(int i=2;i<N;i++){
		if(!ip[i])p[++cnt]=i;
		for(int j=1;j<=cnt&&p[j]*i<N;j++){
			ip[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	ip[1]=1;
	for(int i=1;i<N;i++)g[i]=g[i-1]+!ip[i];
	for(int i=1;i<=M;i++)f[i][0]=i;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=60;j++)
			f[i][j]=f[i][j-1]-f[i/p[j]][j-1];
}
int phi(int i,int j){
	if(i<M&&j<=60)return f[i][j];
	if(!i||!j)return i;
	if(i<N&&p[j]*p[j]>=i)return max(0LL,g[i]-j+1);
	return phi(i,j-1)-phi(i/p[j],j-1);
}
int pi(int n){
	if(n<N)return g[n];
	int k=pow(n,1.0/3);
	int a=g[k];
	int res=phi(n,a)-1+a;
	for(int i=a+1;(int)p[i]*p[i]<=n;i++)
		res-=pi(n/p[i])-pi(p[i])+1;
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();
	int n;
	cin>>n;
	cout<<pi(n);
	return 0;
}

对于公式做些补充与解释：

考虑取 $N=10^9$，那么 $a=\pi(1000)$，此时，公式的前半部分变为 $\phi(10^9,\pi(1000))+\pi(1000)-1$，也就是 $[1,10^9]$ 范围内最小质因子 $>1000$ 以内的最大值数的数的个数 $+1000$ 以内的质数个数（因为它们在第一部分被排除掉了）$-1$（把 $1$ 排除掉）

对于后半部分，我们考察 $\phi(10^9,\pi(10^3))$ 里面包含了什么，显然有着两部分：

1.$>1000$ 的所有质数。

2.由两个 $>1000$ 的质数乘出的合数（$3$ 个乘积必定大于 $10^9$）。

我们只想要第一部分，所以要把第二部分减掉。

我们发现第二部分的每一个数都可以被表示成 $p\times q$ 的形式（其中 $p\le q$ 且 $p,q$ 均为质数同时 $p\le \lfloor\sqrt{n}\rfloor$）。考虑钦定每一个 $p$ 去寻找对应的 $q$，注意到 $q$ 需要同时满足以下几个条件：

1.$q\le \lfloor\frac{n}{p}\rfloor$，否则 $pq>n$。

2.$q\ge p$，毕竟我们就是这么规定的。

所以可行的 $q$ 的数量就是 $[p,\lfloor\frac{n}{p}\rfloor]$ 区间内的质数数量，用前缀和转化一下就是 $\pi(\lfloor\frac{n}{p}\rfloor)-\pi(p-1)$（也可以向上面那样写）。

结合起来就是：

$$\pi(n)=\phi(n,\pi(n^{\frac{1}{3}}))+\pi(n^{\frac{1}{3}})-1-\sum_{n^{\frac{1}{3}}\le p\le \sqrt{n},p\ is\ prime}{\pi(\lfloor\frac{n}{p}\rfloor)-\pi(p-1)}$$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int n=1e7+10,m=1.2e6+10;
int phi[m+5][65],pri[n/10],pre[n],cnt;
//     ^           ^        ^
// 就是$\phi$   质数表  <=i的质数数量 
bool is[n];
//    ^
//是否是质数 

//预处理 
void init(){
	//欧拉筛筛质数
	for(int i=2;i<=1e7;i++){
		if(!is[i])pri[++cnt]=i;
		for(int j=1;j<=cnt && pri[j]*i<=1e7;j++){
			is[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
	is[1]=1;
	
	//前缀和数组处理 
	for(int i=1;i<=1e7;i++)pre[i]=pre[i-1]+!is[i];
	
	//显然p[0]=0，所以phi[i][0]=i;
	for(int i=1;i<=m;i++)phi[i][0]=i;
	
	//利用公式递推 
	for(int i=1;i<=m;i++){
		for(int j=1;j<=60;j++){
			phi[i][j]=phi[i][j-1]-phi[i/pri[j]][j-1];
		}
	}
}

//公式的第一项 
int first(int i,int j){
	//处理过了就直接返回 
	if(i<=m && j<=60)return phi[i][j];
	//有一个为0就直接返回i 
	if(!i || !j)return i;
	//p[j]*p[j]>=i时，所有满足条件的数就是<=i的质数个数-j+1（把p_j补上） 
	if(i<n && pri[j]*pri[j]>=i)return max(0LL,pre[i]-j+1);
	//调公式 
	return first(i,j-1)-first(i/pri[j],j-1);
}

//求答案 
int pi(int x){
	if(x<n)return pre[x];
	int k=pow(x,1.0/3);
	int a=pre[k];
	int res=first(x,a)+a-1;
	for(int i=a+1;pri[i]*pri[i]<=x;i++){
		res-=pi(x/pri[i])-pi(pri[i]-1);
	}
	return res;
}
signed main(){
	int num;
	cin>>num;
	init();
	cout<<pi(num);
	return 0;
}