题解

#include<bits/stdc++.h>//这里用万能头有风险
using namespace std;
typedef long long ll;
const int N=316228;
vector<int> pr;//pr记录素数
bool isprime[N+1];//isprime[i]记录i是否为素数
vector<int> prime(){//这是线性筛
    vector<int> primeFILL;
	fill(isprime,isprime+N+1,true);//初始化
	isprime[0]=isprime[1]=false;//0和1都不是素数
	for(int i=2;i<=N;i++){
		if(isprime[i]){//是素数的话
			primeFILL.push_back(i);//就把这个素数放进去
			for(ll j=(ll)i*i;j<=N;j+=i){
				isprime[j]=false;//素数的倍数一定不是素数
			}
		}
	}
    return primeFILL;//最终返回这个记录好素数的vector
}
ll f(ll n){
	ll ans=0;
	for(int i=0;i<pr.size();i++){
		ll ii=pr[i];
		if(ii*ii*ii*ii>n) break;//以第i个为最小值的三元组答案过大,break
		for(int j=i+1;j<pr.size();j++){
			ll jj=pr[j];
			if(ii*jj*jj*jj>n) break;//同上
			for(int k=j+1;j<pr.size();k++){
				ll kk=pr[k];
				if(ii*ii*jj*kk*kk>n) break;//同上
				ans++;//如果符合要求,那么答案数+1
			}
		}
	}
	return ans;//返回的是答案数
}
int main(){
    pr=prime();//将pr赋值为填充好素数的vector
	ll n;//不开long long见祖宗
	cin>>n;
	cout<<f(n);
	return 0;//华丽收尾
}