普通算法——埃氏筛
埃氏筛
用于更加快速的求素数
思路：
- 创建一个同等大小的bool数组
- 先判断i有没有被筛掉
- 若没有，则以i基数依次筛掉含有该因数i的数，即st[j] = true;
#include <iostream>
#include <ctime>
using namespace std;
const int N = 1e7;
bool st[N] = { false };
int main()
{
double e = clock();
int count = 0;
int pp = 0;
//埃氏筛法：50ms
for (int i = 2; i <= N / i; i++) {
if (!st[i]) {
for (int j = i * i; j < N; j += i) st[j] = true;
}
}
for (int i = 2; i < N; i++)
if (!st[i]) count++;
//普通筛法：806ms
/*for (int i = 2; i < N; i++) {
if (is_Prime(i)) count++;
}*/
//欧拉筛法：43ms
/*int primes[N];
for (int i = 2; i <= N; i++) {
if (!st[i]) primes[pp++] = i, count++;
for (int j = 0; i * primes[j] <= N; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}*/
double s = clock();
cout << count << endl << s - e;
}