我已经得到了一个比较宽松的上界 $O(n^{\frac{3}{4}})$ 和下界 $O(\sqrt n)$。

空间复杂度 $O(\sqrt n)$。

请给出具体的过程，非常谢谢

#include  <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=3.5e6+114;
ll ans,id[Maxn],g[Maxn],cnt;
ll pos1[Maxn],pos2[Maxn];
int p[Maxn],tot;
bitset<Maxn>isp;
inline void init(int N){
	isp[1]=isp[0]=1;
	for(ll i=2;i<=N;i++){
		if(!isp[i]) p[++tot]=i;
		for(ll j=1;p[j]*i<=N;j++){
			isp[i*p[j]]=1;
			if(!(i%p[j])) break;
		}
	}
} 
ll n,sq;
inline ll Get(ll x){
	return x<=sq?pos1[x]:pos2[n/x];
}
int main(){
	scanf("%lld",&n);
	sq=sqrt(n);
	init(sq);
	for(ll l=1,r;l<=n;r=n/(n/l),l=r+1){
		ll v=n/l;id[++cnt]=v;g[cnt]=v-1;
		v<=sq?pos1[v]=cnt:pos2[n/v]=cnt;
	}
	for(ll j=1;j<=tot;j++)
		for(ll i=1;p[j]*p[j]<=id[i];i++)
			g[i]-=g[Get(id[i]/p[j])]-(j-1);
	printf("%lld",g[1]);
	return 0;
}