一篇关于线性筛不错的讲解文章

附上链接:https://zhuanlan.zhihu.com/p/328775914

题目链接:https://leetcode.cn/problems/count-primes/

 1 int countPrimes(int n) {
 2     if(n==0||n==1||n==2)
 3     {
 4         return 0;
 5     }
 6     const size_t size = 5000001;
 7     vector<int> primes;
 8     bitset<size> arr;
 9     size_t j,k;
10     for (size_t i = 2; i < n; ++i)
11     {
12         if (!arr[i])
13         {
14             primes.emplace_back(i);
15         }
16         j=0;
17         k=i*primes[j];
18         while (k<n)
19         {
20             arr[k]=1;
21             if(i%primes[j]==0)
22             {
23                 break;
24             }
25             ++j;
26             k=i*primes[j];
27         }
28         
29     }
30     return primes.size();
31 }