首页 > 代码库 > 埃氏筛法
埃氏筛法
埃氏筛法,理解起来很好理解,就是在1~n这n个连续的数里面开始筛出合数,知道剩下全部为素数,大致流程如下:
第一步:能够确定1不是素数,所以将1筛出,剩下从2开始的数列
第二步:找到2为第一个素数,那么遍历这个数列,将2的倍数筛出,形成一个新的数列
第三步:找到下一个素数 x,此时 x = 3,那么再次遍历这个数列,筛出 x 的倍数,剩下的数再次形成一个新的数列
第四步:重复第三步,直到将所有合数筛出
代码如下:
#include <iostream> #include <cstring> #define N 1000005 using namespace std; int a[N];//存放素数的数组a int b[N];//数字对应表 main() { int n; while( cin >> n )//输入查找上限 { memset( a, 0 ,sizeof(a) ); memset( b, 1 ,sizeof(b) );//下标对应数字为素数则为1,否则为0,全部初始化为1 int t = 0;//记录素数个数的变量 b[0] = 0; b[1] = 0;// 0、1不是素数 for( int i(0); i <= n; i++ )// 遍历不大于n的所有数 { if ( b[i] )//如果这个数为素数 { a[t++] = i; for( int j = 2*i; j <= n; j += i )// 此时i为找到的一个素数,所有 i的倍数都不是素数 b[j] = 0; } } for( int i(0); i < t; i++ ) cout << a[i] <<"\t"; cout << endl << "小于" << n << "的数中,共有" << t << "个素数" <<endl; } }
运行一下就知道,这个筛数法非常的好用,即使输入1e6也能在很短的时间之内筛完,并且开始输出,但是任然存在一个问题,我可不可以不用一直筛到 n?而是在筛到n之前,且完成了将所有合数筛出后就退出呢?
答案是可以的!根据埃氏筛法的结论,我只需要筛到小于√n的那一个素数就行了,至于为什么就不在赘述,既然有了这个结论,很容易就写出来代码
如下:
#include <iostream> #include <cstring> #define N 1000005 using namespace std; int b[N];//数字对应表 main() { int n; while( cin >> n )//输入查找上限 { memset( b, 1 ,sizeof(b) );//下标对应数字为素数则为1,否则为0,全部初始化为1 b[0] = 0; b[1] = 0;// 0、1不是素数 for( int i(0); i*i <= n; i++ )// 遍历不大于n的所有数 if ( b[i] )//如果这个数为素数 for( int j = 2*i; j <= n; j += i )// 此时i为找到的一个素数,所有 i的倍数都不是素数 b[j] = 0; for( int i(0); i < n; i++ ) if( b[i] ) cout << i <<"\t"; } }
两个代码,很明显前面一个会慢一点,但是我能在筛的同时取出素数,而后一个,应为没有遍历整个数组,所以还需要遍历一下整个b数组才能知道哪些是素数。
埃氏筛法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。