c++素數篩選法。本站提示廣大學習愛好者：（c++素數篩選法）文章只能為提供參考，不一定能成為您想要的結果。以下是c++素數篩選法正文

c++素數篩選法

作者：傻蝸牛

素數（又稱質數）：指在大於一的自然數中，只能被1和它自身整除的自然數；

素數篩選法是指一種非常規的素數判定方法，比較高效率；

原理：任何數的整數倍必定不是素數，大於二的偶數必定不是素數。

我們以找出100以內的素數為例，利用原理，我們可以首先排除偶數是素數，然後進一步判斷奇數

實現將偶數標記為0，素數標記為1；（也可以用一個bool數組將偶數標記為false，奇數標記為true）

下面是全部代碼

#include <iostream>
#include <cmath>
#define MAX 100 
using namespace std;

int main()
{
      //設置標記，將偶數標記為0 
      int prime[MAX+1];
      for(int i=1;i<=MAX;i++)
      {
        if(i%2==0)
        {
          prime[i]=0;
        }
        else prime[i]=1;
      }
      
      for(int i=3;i<=sqrt(MAX);i++)
      {
        if(prime[i]==1)
        {
          for(int j=i+i;j<=MAX;j=j+i)
          {
              prime[j]=0;
          }
        }
      }    
      cout<<"2"<<" ";
      for(int i=3;i<=MAX;i++)
      {
        if(prime[i]==1)
        cout<<i<<" ";
      }
  return 0;  
}