admin 管理员组

文章数量: 887006

埃氏筛法，快速求出n范围内的素数个数

如果要求一个数是不是素数，只要求2到√n就行，时间复杂度O（√n）。
但是如果判断多个数字是不是素数，如果还用这种方法的话，就会有许多重复判断的。比如，2是素数，那么4，6，8，10等等，全都不是素数了。因此我们只要知道了2是素数后，就把所有2的倍数给去掉，不用在判断了，然后接下来碰到的最小的数字肯定是一个素数，这就是埃氏筛法。

如图，

把2的倍数去掉后，碰到的是3，三肯定是素数，然后把3的倍数去掉后，碰到的是5，5肯定是素数。

代码奉上：

#include <iostream>
#include <cstring> using namespace std;const int max_n = 1000010;
int prime[max_n];    //储存素数的数组
bool is_prime[max_n];   //标记数组，如果是素数标记位trueint sieve(int n)
{int p = 0;//p就代表了有多少个素数 memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;for (int i=2; i<=n; i++){if (is_prime[i]){prime[p++] = i;for (int j=2*i; j<=n; j+=i){is_prime[j] = false;      把i的倍数都去掉}}}return p;
}int main()
{int n;cin >> n;cout << sieve(n) << endl;return 0;
}

本文标签： 埃氏筛法，快速求出n范围内的素数个数

版权声明：本文标题：埃氏筛法，快速求出n范围内的素数个数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732353222h1533689.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。