欧拉筛
输入 n(n≤100) 个不大于 100000 的整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
- 输入:
5
3 4 5 6 7
- 输出:
3 5 7
代码区：
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
int a[100000],b[100],n,cnt=0;
cin>>n;
int maxn[100001];
memset(a,1,sizeof(a));
a[0]=a[1]=0;
for(int i=2;i<100001;i++)
{
if(a[i])
maxn[cnt++]=i;
for(int j=0;j<cnt;j++)
{
if(i*maxn[j]>100001)
break;
a[i*maxn[j]]=0;
}
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
for(int j=0;j<n;j++)
{
if(a[b[j]])
printf("%d ",b[j]);
}
return 0;
}
埃筛
小A 有一个质数口袋，里面可以装各个质数。他从 2 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。口袋的负载量就是口袋里的所有数字之和。但是口袋的承重量有限，不能装得下总和超过 L(1≤L≤100000)的质数。给出 L，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数个数，所有数字之间有一空行。
- 输入：
100
- 输出
2
3
5
7
11
13
17
19
23
9
代码区：
#include<string.h>
#include<cstdio>
using namespace std;
bool a[10000];
int L;
int main()
{
memset(a,1,sizeof(a));
cin>>L;
a[0]=a[1]=0;
for(int i=2;i<10000;i++)
{
if(a[i])
{
for(int j=2*i;j<10000;j+=i)
{
a[j]=0;
}
}
}
int sum=2,n=0;
for(int i=3;sum<=L;i++)
{
if(a[i-1]){
printf("%d
",i-1);
n++;
}
if(a[i]) sum+=i;
}
printf("%d",n);
return 0;
}