算法基础之筛质数

筛质数

• 核心思想：筛法求质数

埃氏筛法:

• 每次用 2 3 4…. p-1 筛 2 - p之间的数
• 出现2 3 4 …的倍数时 去掉(4实际已经被去掉 不会用4去筛)
• 当2~p-1的数都没有筛掉p 说明p是质数
  • 优化: 只用2~p-1中质数筛

线性筛法:

• 核心: n只会被其最小质因子筛掉

  • 

  • 每一个合数都只会被筛一次，因为每个合数的最小质因数都是唯一的

  •   #include<iostream>
      #include <algorithm>
      
      using namespace std;
      const int N = 1000010;
      
      int prime[N],cnt;
      bool st[N];
      
      void get_prime(int n)
      {
          for(int i = 2;i<=n;i++)
          {
              if(!st[i]) prime[cnt++] = i;  //如果没被筛掉 记录成质数
              for(int j = 0;prime[j] <= n/i ; j ++)  //从小到大遍历所有质数
              {
                  st[prime[j] * i] = true;  //将prime[j]的倍数筛掉
                  if(i % prime[j] == 0) break;  //如果i % prime[j] == 0 说明i是prime[j]的倍数
                  							  //那么当prime[j+1]的时候 prime[j+1]*i的最小质因数是prime[j] 而不是prime[j+1]
              }
          }
      }
      
      int main()
      {
          int n;
          cin>>n;
          
          get_prime(n);
          
          cout<<cnt;
      }