题目大意: 给定整数 n, 请问 n 以内有多少个素数
思路: 想必要判断一个数是否是素数, 大家都会了, 并且可以在 O(根号 n) 的复杂度求出答案, 那么求 n 以内的素数呢, 那样求就显得有点复杂了, 下面看一下这里介绍的?? 氏算法
其实呢, 就是求出第一个素数, 然后把 n 以内它的倍数都删掉就行了, 很简单. 然后找下一个素数, 同样方法.....
看代码
- #include<iostream>
- #include<string.h>
- #include<map>
- #include<cstdio>
- #include<cstring>
- #include<stdio.h>
- #include<cmath>
- #include<math.h>
- #include<algorithm>
- #include<set>
- #include<queue>
- typedef long long ll;
- using namespace std;
- const ll mod=1e9+7;
- const int maxn=1e6+10;
- const int maxk=5e3+10;
- const int maxx=1e4+10;
- const ll maxe=1000+10;
- #define INF 0x3f3f3f3f3f3f
- #define Lson l,mid,rt<<1
- #define Rson mid+1,r,rt<<1|1
- int n;
- int prime[maxn];
- bool is_prime[maxn];
- void solve()
- {
- int sum=0;
- memset(is_prime,false,sizeof(is_prime));
- is_prime[0]=is_prime[1]=true;
- for(int i=2;i<=n;i++)
- {
- if(!is_prime[i])
- {
- prime[sum++]=i;
- for(int j=i*2;j<=n;j+=i)
- {
- is_prime[j]=true;
- }
- }
- }
- cout<<sum<<endl;
- }
- int main()
- {
- cin>>n;
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2716551.html