希望大家仔细阅读，能够学有所成！

埃式筛法

首先要了解什么式埃式筛法之前，需要知道一个定理。

就是素数的整数倍一定不是素数。

了解了这个就基本大概懂了埃式筛法。

• 首先初始化一个布尔数组is_prime，用于记录每个数是否为素数。

• 从2开始，枚举每个数i，如果is_prime[i]为true，则i是素数，添加到素数数组primes中。

• 然后对于每个i，我们让我扩大j倍，直到ij小于输入的数字n，把is_prime[i j]赋值为false。

• 重复步骤2和3，直到遍历到n为止。

埃式筛法求解某一个数字包含的所有素数数组

Code

#include<iostream>
include<vector>
include<ctime>
usingnamespacestd;
vector<int>sieve_of_eratosthenes(intn){
vector<int>primes;
vector<bool>is_prime(n+1,true);
is_prime[0]=is_prime[1]=false;
for(inti=2;i<=n;i++){
if(is_prime[i]){
primes.push_back(i);
}
for(intj=2;ij<=n;j++){
is_prime[ij]=false;
}
}
returnprimes;
}
intmain(){
clock_tstart,end;
start=clock();
intn;
cout<<"PleaseEntern:";
cin>>n;
vector&lt;int&gt;primes=sieve_of_eratosthenes(n);cout&lt;&lt;&quot;Primes:&quot;;for(intprime:primes){ cout&lt;&lt;prime&lt;&lt;&quot;&quot;;}cout&lt;&lt;&quot;\n素数个数为&quot;&lt;&lt;primes.size()&lt;&lt;&quot;个\n&quot;;end=clock();cout&lt;&lt;&quot;Theruntimeis:&quot;&lt;&lt;(double)(end-start)/CLOCKS_PER_SEC&lt;&lt;&quot;s&quot;&lt;&lt;endl;return0;
}

运行结果

埃式筛法判断某一个数字是否为素数

Code

#include<iostream>
include<vector>
include<ctime>
usingnamespacestd;
//埃式筛法求解素数
boolsieve_of_eratosthenes(intn){
vector<bool>is_prime(n+1,true);
is_prime[0]=is_prime[1]=false;
for(inti=2;i<=n;i++){
if(is_prime[i]&&i==n){
returntrue;
}
for(intj=2;ij<=n;j++){
is_prime[ij]=false;
if(i*j==n){
returnfalse;
}
}
}
}
intmain(){
clock_tstart,end;
start=clock();
intn;cout&lt;&lt;&quot;PleaseEntern:&quot;;cin&gt;&gt;n;if(sieve_of_eratosthenes(n)){ cout&lt;&lt;n&lt;&lt;&quot;是素数!!!&quot;;}else{ cout&lt;&lt;n&lt;&lt;&quot;不是素数...&quot;;}end=clock();cout&lt;&lt;&quot;Theruntimeis:&quot;&lt;&lt;(double)(end-start)/CLOCKS_PER_SEC&lt;&lt;&quot;s&quot;&lt;&lt;endl;return0;
}

运行结果