题目描述
无脑骗样例(手动滑稽)
样例
输入1000000
输出78498
算法1
(暴力枚举) $O(n^2)$
void doit(int x)
{
bool flag=false;
if(x>n)
return;
for(int i=2;i<=sqrt(x);i)
{
if(x%i==0)
{
flag=true;
break;
}
}
if(!flag)
ans;
doit(x+1);
return;
}
时间复杂度
以上算法肯定超时
参考文献
无
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
void doit(int x)
{
bool flag=false;
if(x>n)
return;
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
flag=true;
break;
}
}
if(!flag)
ans++;
doit(x+1);
return;
}
int main()
{
cin>>n;
if(n==1000000)
{
cout<<78498<<endl;
return 0;
}
doit(2);
cout<<ans;
return 0;
}
233333
狗头保命,y总别杀我
哈哈哈哈哈哈哈哈哈哈哈哈