先判断素数再判断最大质因数,时间复杂度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;\
}\