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

先判断素数再判断最大质因数,时间复杂度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(isprime(i)&&i<=b){\
//			cnt++;continue;\
//		}\
		if(maxprime(i)<=b)cnt++;\
//		cout<<cnt<<endl;\
//		system("pause");\
	}\
	cout<<cnt<<endl;\
	return 0;\
}\
2024/9/14 13:51
加载中...