普通算法——埃氏筛
埃氏筛用于更加速速的求素数
思路：
[*]创建一个划一大小的bool数组
[*]先判断i有没有被筛掉
[*]若没有，则以i基数依次筛掉含有该因数i的数，即st = true;
#include <iostream>
#include <ctime>
using namespace std;
const int N = 1e7;
bool st = { false };
int main()
{
double e = clock();
int count = 0;
int pp = 0;
//埃氏筛法：50ms
for (int i = 2; i <= N / i; i++) {
if (!st) {
for (int j = i * i; j < N; j += i) st = true;
}
}
for (int i = 2; i < N; i++)
if (!st) count++;
//普通筛法：806ms
/*for (int i = 2; i < N; i++) {
if (is_Prime(i)) count++;
}*/
//欧拉筛法：43ms
/*int primes;
for (int i = 2; i <= N; i++) {
if (!st) primes = i, count++;
for (int j = 0; i * primes <= N; j++) {
st * i] = true;
if (i % primes == 0) break;
}
}*/
double s = clock();
cout << count << endl << s - e;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]