埃拉托斯特尼筛法（素数高效筛选）

本文主要是介绍埃拉托斯特尼筛法（素数高效筛选），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、素数定义

素数又称质数（prime number），指所有大于1的数中只能被1和它本身整除的数。

二、埃拉托斯特尼筛法（Sieve of Eratosthenes）

1.算法的基本思想：

如果一个数是质数，那么它的倍数肯定非质，利用事先定义的线性表以打表方式标记非质，则剩下的数就是素数。

2.筛选过程：

三、算法实现

   char *p_sieve=new char[num+1];memset(p_sieve,'1',num*sizeof(char)+1);   //预先置全部数为素数for(unsigned long i=2;i<=sqrt(num);i++)    //循环从4开始，2 3都是素数所以这样跳过没有问题{if(p_sieve[i]=='0')        //已经处理过的数跳过continue;for(unsigned long j=i*i;j<=num;j+=i)    //检测到素数，剔除它的倍数，质为非质p_sieve[j]='0';}

四、类实现

#include <iostream>
#include<memory.h>
#include<cmath>
using namespace std;
class CSieve
{
private:char *p_sieve;unsigned long num;                //numÊÇ×î´ó·¶Î§void Excute_Prime();
public:CSieve(unsigned long n);void printPrime();~CSieve();
};
CSieve::CSieve(unsigned long n)
{num=n;p_sieve=new char[num+1];memset(p_sieve,'1',num*sizeof(char)+1);   //预先置全部数为素数Excute_Prime();
}
void CSieve::Excute_Prime()
{for(unsigned long i=2;i<=sqrt(num);i++)    //循环从4开始，2 3都是素数所以这样跳过没有问题{if(p_sieve[i]=='0')        //已经处理过的数跳过continue;for(unsigned long j=i*i;j<=num;j+=i)    //检测到素数，剔除它的倍数，质为非质p_sieve[j]='0';}
}
void CSieve::printPrime()
{for(unsigned long i=2;i<=num;i++)  if(i==2)cout<<i;elseif(p_sieve[i]-'0')cout<<" "<<i;cout<<endl;
}
CSieve::~CSieve()
{delete p_sieve;
}/******************************测试代码*****************************************/
int main()
{int txt_time;unsigned long n;cin>>txt_time;while(txt_time--){cin>>n;CSieve one_solve(n);one_solve.printPrime();}return 0;
}