Submission #41056710

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int p[N],cnt,num[N],s[N],L[N],R[N],ans,tot[N];
bool is[N];
signed main(){
	memset(is,1,sizeof is);
	is[1]=0; 
	int n;
	cin>>n;
	for(int i=2;i*i<=n;++i){
		s[i]=s[i-1]+is[i];
		if(is[i]){
			tot[i]=num[i]=1;
			L[i]=R[i]=i;
			p[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*i*p[j]*p[j]<=n;++j){
			is[i*p[j]]=0;
			tot[i*p[j]]=tot[i]+1;
			if(i%p[j]){
				num[i*p[j]]=num[i]+1;
				L[i*p[j]]=p[j];
				R[i*p[j]]=R[i];
			}else{
				num[i*p[j]]=num[i];
				L[i*p[j]]=L[i];
				R[i*p[j]]=R[i];
				break;
			}
		}
	}
	for(int i=sqrt(n);i>=10;--i){
		if(num[i]!=2||tot[i]!=2){
			continue;
		}
		int k=n/(i*i);
		if(k<=L[i]){
			continue;
		}
		if(R[i]-L[i]<=1){
			continue;
		}
		ans+=s[min(k,R[i]-1)]-s[L[i]];
	}
	cout<<ans;
}

Submission Info

Judge Result