首页 > 代码库 > 筛素数
筛素数
整理一下筛素数的方法
我在网上了解到两种筛素数的方法
一种是 1/3n*判断 的时间复杂度
一种是的时间复杂度应该是比这个低
先说一下第一种的思路
首先：一个数如果他除以一个素数除不尽，那么他除以该素数的倍数也除不尽
所以我们可以这么考虑
如果一个数是二或三的倍数 那么它一定不是素数
于是 对于 1 2 3 4 5 6 7 8 9 10 11 12……
那么排除2和3的倍数
剩下的是 1 5 7 11 ……
对于六个数
6*n 6*n+1 6*n+2 6*n + 3 6*n + 4 6*n + 5
只需要检测 6*n+1 和6*n+5是不是素数就可以了
然后就是小的优化了
判断一个数x是不是素数
一种是枚举2~x-1 一种是2~sqrt(x) 都不是最优化的
由于之前已经存储了一些素数 可以枚举这些素数来判断 因为如果一个数除以一个素数除不尽 那么除以该素数的倍数一定除不尽
第二类有很多种优化
先写一下最原始的代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const int maxn = 105; 8 int flag[maxn], prm[maxn]; 9 10 int get(int n) {11 int k = 0;12 memset(flag, 1, sizeof(flag));13 for(int i = 2; i <= n; i++) {14 if(flag[i]) {15 prm[k++] = i;16 for(int j = i; j <= n; j += i) {17 flag[j] = 0;18 }19 }20 }21 return k;22 }23 24 int main() {25 int k = get(100);26 for(int i = 0; i < k; i++) {27 printf("%d ", prm[i]);28 } puts("");29 }
思路 是大一刚开学在杭电的一个题解上看到的
首先 2是素数 那么 2的倍数4 6 8……就一定不是素数
然后3是素数 那么 3的倍数也就一定不是素数
但是这种方法有很大的缺点
就是比如删除2的倍数的时候 会删到6 12 18等而删3的倍数的时候也会删到 于是造成了删除的冗余 所以该算法的执行效率一般
而接下来的优化全部都是对于这个方向的优化
第一中优化是来自一篇博客
他的思路是这样的
一个数如果不是素数那么他的因子一定有他小的素数
那么对于每个数i只要把i之前的所有素数都乘以i那么 就不会错过下一个数i+1是不是合数
这个方法应该能理解
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;const int maxn = 105;int flag[maxn], prm[maxn];int get(int n) { int k = 0; memset(flag, 1, sizeof(flag)); for(int i = 2; i <= n; i++) { if(flag[i]) { prm[k++] = i; } for(int j = 0; j < k && prm[j] * i <= n; j++) { flag[prm[j] * i] = 0; } } return k;}int main() { int k = get(100); for(int i = 0; i < k; i++) { printf("%d ", prm[i]); } puts("");}
还有一个优化 明早起来写
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const int maxn = 105; 8 int flag[maxn], prm[maxn]; 9 10 int get(int n) {11 int k = 0;12 memset(flag, 1, sizeof(flag));13 for(int i = 2; i <= n; i++) {14 if(flag[i]) {15 prm[k++] = i;16 }17 for(int j = 0; j < k && prm[j] * i <= n; j++) {18 flag[prm[j] * i] = 0;19 if(i % prm[j] == 0) 20 break;21 }22 }23 return k;24 }25 26 int main() {27 int k = get(100);28 for(int i = 0; i < k; i++) {29 printf("%d ", prm[i]);30 } puts("");31 }
筛素数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。