邪恶的TLE又又又又在呼吸,必须制裁
查看原帖
邪恶的TLE又又又又在呼吸,必须制裁
1094880
liuchijun楼主2024/9/14 13:55

纯暴力,时间复杂度o(pow(n,1.5))o(pow(n,1.5))
为什么会炸?崩溃了我真的崩溃了!
上网一查,基本没有埃氏筛法及欧拉筛法是对的
家人们谁懂啊!

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
bool isprime(ll x){
	if(x==2)return true;
	for(ll i=2;i<=sqrt(x);i++){
		if(x%i==0)return false;
	}
	return true;
}

ll maxprime(ll x){
	ll ret;
	for(ll i=x;i>=2;i--){
		if(x%i==0&&isprime(i)){
			ret=i;break;
		}
	}
	return ret;
}

int main()
{
	ll cnt=0;
	ll n,b;
	cin>>n>>b;
	for(ll i=1;i<=n;i++){
		if(maxprime(i)<=b)cnt++;
//		cout<<cnt<<endl;
//		system("pause");
	}
	cout<<cnt<<endl;
	return 0;
}
2024/9/14 13:55
加载中...