基本思想:
用筛法求素数的基本思想是:把从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的数的倍数不为素数,通过大内存换取少时间;
好像时间复杂度更大。。。。。。。
0.0分
6 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:505 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:529 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:443 |
C二级辅导-同因查找 (C语言代码)浏览:585 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
买不到的数目 (C++代码)浏览:868 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1099 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:937 |
K-进制数 (C语言描述,蓝桥杯)浏览:925 |
字符逆序 (C语言代码)浏览:460 |