c++素数筛选法_C/C++

c++素数筛选法

2021-05-13 13:39傻蜗牛 C/C++

本文讲的是筛选法的C++实现，筛选法又称筛法，是求不超过自然数N（N>1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。

素数（又称质数）：指在大于一的自然数中，只能被1和它自身整除的自然数；

素数筛选法是指一种非常规的素数判定方法，比较高效率；

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

我们以找出100以内的素数为例，利用原理，我们可以首先排除偶数是素数，然后进一步判断奇数

实现将偶数标记为0，素数标记为1；（也可以用一个bool数组将偶数标记为false，奇数标记为true）

c++素数筛选法

下面是全部代码

				?

									#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;  

									}