基本思想:

用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有:

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:

2 3 5 7 11 13 17 19 23 29

参考代码:

#include<cstdio>
using namespace std;
int an[1000000]={0};//初始化所有数值为0
int main ()
{
 int n;
 scanf("%d",&n);
 for(int i=2;i<=n;i++)//从2到n开始循环
 {
      if(!an[i])//如果未被判断不是素数的话,进入循环开始判断
          for(int j=4;j<i;j++)//从4到需要判断的数开始循环(因为从2,3开始都会遗漏2,3)
            if(i%j==0)//如果要被判断的数能被整除则令此数为1
              an[i]=1;
      if(!an[i])//既然此数是素数,那么它的倍数必定不是素数
      for(int t=i*2;t<=n;t+=i)//对其倍数赋值为1;
             an[t]=1;
 }
 for(int i=2;i<=n;i++)
     if(!an[i])
     printf("%d\n",i);
 return 0;
}

还有一个提交后用时几乎为0的代码:

#include<cstdio>
using namespace std;
int an[1000000]={0};//初始化所有数值为0
int main ()
{
 int n;
 scanf("%d",&n);
 for(int i=2;i<=n;i++)//从2到n开始循环
 {
      if(!an[i])//如果未被判断不是素数的话,进入循环开始判断
          for(int j=4;j<i;j++)//从4到需要判断的数开始循环(因为从2,3开始都会遗漏2,3)
            if(i%j==0)//如果要被判断的数能被整除则令此数为1
              {
              an[i]=1;
              for(int t=i*2;t<=n;t+=i)//对其倍数赋值为1;
             an[t]=1;
          }
      if(!an[i])//既然此数是素数,那么它的倍数必定不是素数
      for(int t=i*2;t<=n;t+=i)//对其倍数赋值为1;
             an[t]=1;
 }
 for(int i=2;i<=n;i++)
 if(!an[i])
 printf("%d\n",i);
 return 0;
}

区别就在于利用任何大于2的数的倍数不为素数,通过大内存换取少时间;

好像时间复杂度更大。。。。。。。图片1.png

点赞(1)
 

0.0分

6 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 1 条评论

郝润平 4年前 回复TA
讲的很清楚