C++14(g++5.4) 解法, 执行用时: 821ms, 内存消耗: 24176K, 提交时间: 2020-10-16 19:59:28

#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long 
#define maxn 1000005
using namespace std;

ll n,i,j,k,ans,pri[maxn],mp[maxn],tot,bz[maxn];

void getpri(){
	for(ll i=2;i<maxn;i++){
		if (!bz[i]) pri[++tot]=i,mp[tot]=1ll*i*i;
		for(ll j=1;j<=tot&&i*pri[j]<maxn;j++){
			bz[i*pri[j]]=1;
			if (i%pri[j]==0) break;
		}
	}
}

ll cnt,id1[maxn],id2[maxn]; ll g[maxn],f[maxn];

ll doit(ll n){
	ll i,j,B=sqrt(n);
	for(ll i=1;i<=n;i=j+1){
		j=n/(n/i),g[++cnt]=n/i;
		if (n/i<=B) id1[n/i]=cnt;
		else id2[n/(n/i)]=cnt;
		f[cnt]=g[cnt]-1;
	}
	for(j=1;j<=tot&&mp[j]<=n;j++)
		for(i=1;i<=cnt&&mp[j]<=g[i];i++){
			k=(g[i]/pri[j]<=B)?id1[g[i]/pri[j]]:id2[n/(g[i]/pri[j])];
			f[i]=f[i]-f[k]+j-1;
		}
	return f[1];
}

int main(){
	scanf("%lld",&n),getpri();
	ans=doit(n);
	for(i=1;mp[i]<=n;i++){
		ll x=mp[i];
		while (x<=n) ans++,x*=pri[i];
	}
	printf("%lld",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 389ms, 内存消耗: 15736K, 提交时间: 2020-10-16 22:57:40

#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=7e5;
ll i,j,k,n,sqr,p[N],x,ans,m,w[N],g[N],id1[N],id2[N];
bool bz[N];
int main()
{
	scanf("%lld",&n),sqr=sqrt(n);
	fo(i,2,sqr)
	{
		if(!bz[i])
		{
			p[++p[0]]=i;
			for(ll t=n/i;t>=i;t/=i)
			ans++;
		}
		for(j=1;(j==1||i%x)&&i*(x=p[j])<=sqr;j++)
		bz[i*x]=1;
	}
	fo(i,1,n)
	{
		j=n/(w[++m]=n/i);
		w[m]<=sqr?id1[w[m]]=m:id2[n/w[m]]=m;
		g[m]=w[m]-1;
		i=j;
	}
	fo(j,1,p[0])
	fo(i,1,m)
	{
		if(p[j]*p[j]>w[i])
		break;
		k=((x=w[i]/p[j])<=sqr)?id1[x]:id2[n/x];
		g[i]-=g[k]-(j-1);
	}
	printf("%lld",ans+g[1]);
}