埃特里尼质数筛法

Cpandafighting · 2020-01-25 19:26:10 · 个人记录

小A 有一个质数口袋，里面可以装各个质数。他从 2 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。口袋的负载量就是口袋里的所有数字之和。但是口袋的承重量有限，不能装得下总和超过 L(1\le L\le100000)L(1≤L≤100000) 的质数。给出 L，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数个数，所有数字之间有一空行。

输入 100

输出 2 3 5 7 11 13 17 19 21 9

核心思想： 这道题目主要是讲的埃氏筛法，它的核心思想是：如果n是质数，那么2n,3n,4n,...这些n的倍数肯定都不是质数。

其次，如果选的数要多，那么要选的每个数要尽可能小。

时间复杂度是（nloglogn）//不管自然对数，一般默认为2

AC代码： //关于素数的解法(埃特里尼质数筛法)

include<stdio.h>

include<math.h>

include<stdlib.h>

{

int i,j;

int l,count=0; //总和

int prime[100001];
memset(prime, 1, sizeof(prime));//埃筛必须初始化,如果不是素数就输出0；
prime[0]=0;
prime[1]=0;
scanf("%d",&l);
for(i=2;i<100000;i++)
{
     if(prime[i])
     {
         if(j=i*2;j<100000;j+=i)  //如果这个数是素数的2倍，3倍，4倍，那么它肯定不是素数。
         {
            prime[j]=0; 
         }
     }
}
for(i=2;i<100000;i++)
{
    if(prime[i])
    {
        if(l>=i)
        {
            printf("%d\n",i);
            l-=i;
            count++;
        }
    }
}
printf("%d\n",count);

}

数据结构（王卓）：https://www.bilibili.com/video/av31223406 （她的课相当不错，讲得很细，然而数据结构只是提供思想，代码还得自己完成。。。） //https://www.luogu.com.cn/problemnew/solution/P3383 //有关素数的八种方法