质数筛法

前置：

​​

​​

埃氏筛法

1. 直接举例子（从 2~n）

   2 是质数，而 4、6、8 不是
   3 是质数，6、9 不是
   4 不是质数
   5 是质数
   6 不是质数
   7 是质数
   8 不是质数
   9 不是质数

   说明：从 2 开始遍历开始筛，那么当遍历到一个数时它还没有被筛掉，它就一定是质数——因为说明在它之前它没有被质因数筛过。

2. 上代码

   #include<iostream>
   using namespace std;
   
   const int N = 1000010;
   
   int primes[N], cnt; //存筛出来的质数
   bool st[N];//初始为false，置st[x] = true说明x是合数
   
   void get_primes(int n)
   {
       for (int i = 2; i <= n; i ++){
           if(st[i]) continue;
           primes[cnt++] = i;
           for(int j = i; j <= n; j += i)
           {
               st[j] = true;
           }
       }
   }
   
   int main()
   {
       int n;
       cin >> n;
       get_primes(n);
   
       cout << cnt << endl;
       return 0;
   }
   ​

3. 时间复杂度

   • ​O(nlogn)​

   • 计算过程

     void get_primes(int n)
     {
         for (int i = 2; i <= n; i ++){
             if(st[i]) continue;		//n次
             primes[cnt++] = i;	//n次
             for(int j = i; j <= n; j += i) //次数是n/i次
             {
                 st[j] = true;
             }
         }
     }
     //n + n + n/1 + n/2 + ... + n/n = 2n + O(nlogn)
     ​

4. 缺点——从上面的例子中能够看出来，有的数会被筛多次，比如 6 被 2 和 3 各筛过一次。而线性筛就是优化了这个问题

线性筛法

1. 算法特性：每个数都只会被自己的最小质因数筛、且只筛一次。

2. 因为比较抽象，直接上代码，仔细讲解代码

   void get_primes(int n)
   {
       for(int i = 2; i <= n; i ++){	//保证每个数都会过一遍
           if(!st[i]) primes[cnt ++] = i;	//如果此前没有被筛过说明它就是质数
   
           for(j = 0; primes[j] <= n/ i; j ++){
               st[primes[j] * i] = true;
               if(i % primes[j] == 0) break;
           }
       }
   }
   ​

3. 时间复杂度

   • ​O(n)​

   • 计算过程

     void get_primes(int n)
     {
         for(int i = 2; i <= n; i ++){
             if(!st[i]) primes[cnt ++] = i;//执行n遍
     
             for(j = 0; primes[j] <= n/ i; j ++){ //因为线性筛的特点，这里i从2到n也就会执行n遍
                 st[primes[j] * i] = true;
                 if(i % primes[j] == 0) break;
             }
         }
     }
     
     //n + n = 2n
     ​