普通算法——埃氏筛

埃氏筛

用于更加速速的求素数
思路：

• 创建一个划一大小的bool数组
  
• 先判断i有没有被筛掉
  
• 若没有，则以i基数依次筛掉含有该因数i的数，即st[j] = true;
  

1. #include <iostream>
2. #include <ctime>
3. using namespace std;
5. const int N = 1e7;
7. bool st[N] = { false };
9. int main()
10. {
11.         double e = clock();
12.         int count = 0;
13.         int pp = 0;
14.         //埃氏筛法：50ms
15.         for (int i = 2; i <= N / i; i++) {
16.                 if (!st[i]) {
17.                         for (int j = i * i; j < N; j += i) st[j] = true;
18.                 }
19.         }
20.         for (int i = 2; i < N; i++)
21.         if (!st[i]) count++;
22.         //普通筛法：806ms
23.         /*for (int i = 2; i < N; i++) {
24.                 if (is_Prime(i)) count++;
25.         }*/
26.         //欧拉筛法：43ms
27.         /*int primes[N];
28.         for (int i = 2; i <= N; i++) {
29.                 if (!st[i]) primes[pp++] = i, count++;
30.                 for (int j = 0; i * primes[j] <= N; j++) {
31.                         st[primes[j] * i] = true;
32.                         if (i % primes[j] == 0) break;
33.                 }
34.         }*/
35.         double s = clock();
36.         cout << count << endl << s - e;
37. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。