【简单总结请直接翻到最后讨论部分】

素数筛

基本介绍

素数问题是数学领域中的基本问题，也是程序设计或者面试笔试中的常见问题。计算机的诞生，让素数的计算过程大大加快。

本文是这段时间我个人学习素数相关知识的阶段性总结，也是对知识的记录和分享。

希望和大家一起学习、一起进步。以后还会陆续更新其他方面的知识。

首先，明确素数的定义：

质数(素数)是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。—“质数(素数)百度百科”

根据素数这一定义，可以提炼出几点内容

1. 素数是自然数，因此是整数
2. 素数是大于1的自然数，因此小于等于1的数字都不是素数（包括负数，0和小数）
3. 素数只有两个因数，1和自身
4. 结合1,2,3点，可以推断出，在自然数范围内，最小的素数是2

同时根据这一定义，发展出许多计算素数的方法，以下让我一一介绍。

算法

一、朴素算法求素数

1.1、 试除法

朴素算法里只是根据素数的定义而设计的算法。

根据素数的定义：素数只有两个因子，1和自身。因此如果有其他因子的数字，都不是素数。根据这一结论，采用试除法，在[2，n-1]范围内，逐一枚举数字$i$，去判定$i$是否为该数字的因子，从而根据素数定义去判定该数是否为素数。

程序代码 时间复杂度为$O(n)$

#include <bits/stdc++.h>
using namespace std;
int IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。        
    for(int i=2;i<n;i++)//逐个判断【2，n-1】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}
int main(){
	int n;
    printf("请输入要检验的数字\n");
    while(scanf("%d",&n)!=EOF){
        if(IsPrime(n)==1)
            printf("%d是素数\n\n",n);
        else
            printf("%d不是素数\n\n",n);
    }
    return 0;
}

1.2、优化方法一

一个数字$n$如果有其中一个因子$a$,则必然存在另外一个因子$b$（$a,b$可能相等$）$，即$n=a*b$的形式。显然一个数的因子$i$,除了1和它本身以外，符合 $2\le i \le (n/2)$

因此上述代码的枚举范围可以缩小到n/2。

程序代码

时间复杂度为$O(n/2)$

int IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。        
	for(int i=2;i<=n/2;i++)//逐个判断【2，n/2】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}

1.3、优化方法二

我们再分析，根据$n=a*b$，我们可以假设$a\le b$ ，显然$n$的因子一定是成对出现的，例如100的因子有如下关系：

n=	a	*b
$100=$	$1$	$*100$
	$2$	$*50$
	$4$	$*25$
	$5$	$*20$
	$10$	$*10$

我们只需要找到其中1个因素a即可判断n是否为素数了，根据分析$2\le a \le \sqrt{n}$，所以我们只需要在$a$的范围内枚举$i$即可

程序代码

时间复杂度为$O(\sqrt{n})$

bool IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。 
  int m=sqrt(n);//尽量不要在循环体内进行开根号运算
	for(int i=2;i<=m;i++)//逐个判断【2，sqrt(n)】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}

$i\le \sqrt{n}$的另外一种表示形式$i*i\le n$ 理论上比前者更高效简洁一点，但是要注意$i*i$不要超出数据范围，代码如下：

bool IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。 
	for(int i=2;i*i<=n;i++)//逐个判断【2，sqrt(n)】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}

1.4、优化方法三

我们继续思考，除了2以外的偶数一定不是素数，我们把这种情况去掉，又可以少一半的判断次数了

程序代码

#include <bits/stdc++.h>
using namespace std;
bool IsPrime(int n){
    if(n<2)return false; //最小的素数是2，因此小于2的数字都是非素数。 
    if(n!=2 && n%2==0)return false;
	for(int i=2;i*i<=n;i++)//逐个判断【2，sqrt(n)】范围内有无其他因子
        if(n%i==0)return false;
    return true;
}
int main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(Isprime(i))ans++;
	}
	cout<<ans;
	return 0;
}

如果是判断1-n之间有几个素数，那么时间复杂度为$O(n/2 * \sqrt{n})$；

二、筛法求算法

3、素数筛-埃氏筛(埃拉托斯特尼筛法)

这里介绍另外一种找素数的方法。

上面的朴素算法以及各种优化方法，都是对给定的单一数字进行判断，从而得知这个数字是否为素数。但在实际问题中，往往需要获取一个区间内所有素数，或者在短时间内多次查询判断。应对这样的需求，我们会进行预处理：对某一区间进行素数挑选，把素数挑选出来，存储到另外一个地方或者标记起来。

要实现这样的预处理，使用上面的朴素算法，就需要双层循环，这样时间复杂度大概是O(n^2)

接下来介绍的这两种算法，正好是把某一区间内的素数都筛选出来，且时间复杂度也不高。

3.1、简单介绍–引入 让我们再次回顾素数(质数)的定义

质数(素数)是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。—“质数(素数)百度百科”

上面的朴素算法，我们是尝试把数字拆分为因子相乘的形式，对范围区间内的数字进行判断时，，则需要对每个数字都进行拆分，那么我们是否可以使用另外一种方式呢？

这里我们选择另外一种方式：反向构造。

我们事先不知道一个数是否为素数，但是我们可以创造出合数（非素数）。

数字可以划分为素数和合数两大类，那么当我们把某一范围内的合数都标记出来，则剩下的数字就是素数。

如何构造合数呢？在大于1的数字中任取两个数字a，b相乘即可，这样得到的结果c必然有1，a，b，c四个因子（当a=b时为三个因子）那么c必然是合数

总结成算法就是

设定两个数组，一个数组包括范围内的所有数字，用来标记此数字是否被访问过；另外一个数组用来存储已经筛选出来的素数（如果仅仅是查询某个数是否为素数，则访问数组就可以实现这个功能，素数数组是方便筛选过程结束后可以输出筛选出的素数） 将访问数组中访问标记设为未访问，将素数数组清空，将0，1等非素数访问标记设为已访问（素数标记是设为未访问还是已访问，根据自己的逻辑习惯设定） 从2开始循环，直到范围的上界，判断每一个数字是否被访问过，访问过的是非素数（合数），未访问过的是素数 接着对这个数字进行倍增操作，从两倍开始，直到若干倍后到达上界为止，这其中得到的数字结果的访问标记都设为已访问。重复步骤3,4，直至3中循环结束 这里步骤4中是第二个循环，用来进行倍增操作，凡是在此过程中得到的数字，都是构造出来的合数。而步骤3中，循环到当前数字未被访问过，则此数字是素数。因为如果此数字是合数的话，那么它的因子一定是小于自身的。那么在前面从小数开始循环的时候，就会遇到因子，更会在这个因子倍增的过程中，把数字给标记掉。所以如果步骤3访问当某个数字是未标记时，那么这个数字一定是素数。

举例说明：12是合数，有2,3,4,6；从小数开始循环、倍增时，2倍增时会把12标记掉，同样地，3,4,6也会把12标记掉。所以如果访问到a未被标记，那么a一定是素数

这个算法的好处就是，利用了一次倍增，得到了后面若干个数字的结果。循环到这些数字的时候，就不再需要花时间去计算，直接可以得到结果。这里用了一个必不可少的标记数组，花费了一定的空间。**这里实际上就是典型的用空间来换取时间。**花费更多的内存空间，来换取时间的减少。时间和空间的取舍，也讲求经济性

程序代码

这里就不提时间复杂度了。这里整个过程像个筛子一样，把不要的合数筛下去，剩下的就是所需的素数。

#include<stdio.h>
#include<string.h>//memset函数的头文件

//设定一个宏，定义数组大小
#define maxn 20010

int vis[maxn];//vis用来判断数字是否访问过
int prime[maxn];//prime用来存储筛选出来的素数


int sieve(int n)
{
    int i,j,k;
    k=0;//i用来控制逐个访问，j用来第二轮标记，k用来标记prime数组位置
    //这里在函数中置为0，保证每一次函数调用时都清空，不会受到上次使用完后的结果
    //理论上需要这样做，但是在此程序中可以省略，因为数字范围彼此之间是子集的关系，而范围的改变不会改变数字的性质
    memset(vis,0,sizeof(int)*maxn);//将访问数组清零。可以使用short或者C++的bool类型节省内存、
    vis[0]=vis[1]=1;//将0和1标记为已访问，不标记其实也可以，因为我们素数的计数是从2开始
    for(i=2;i<=n;i++)//从最小的素数2开始筛选，2以下就没必要筛选
    {
        if(vis[i]==0)//这个数是目前最小的，且未被访问过的
            prime[k++]=i;//因此这个数是素数
        for(j=2;i*j<=n;j++)//j表示倍数，从两倍开始倍增，直到上界为止
            vis[i*j]=1;//将倍数标记为已访问
    }
    return k;//返回范围内素数的个数
}

void print(int k)//打印结果函数
{
    int i;
    for(i=0;i<k;i++)
    {
        printf("%5d ",prime[i]);//每个数字占5个宽度，右对齐，保持输出结果整洁
        if((i+1)%5==0)//每五个为一组换行
            printf("\n");
    }
    printf("\n\n");
}

int main()
{
    int n;//求n以内的素数
    int k;//保存返回的素数个数
    while(scanf("%d",&n)!=EOF)
    {
        k=sieve(n);
        if(k==0)
            printf("(1-%d]范围内没有素数\n",n);
        else
            printf("(1-%d]范围内的素数有:\n",n);
        print(k);
    }
}

函数中另外一种写法

int sieve(int n)
{
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
            prime[k++]=i;
        for(j=i+i;j<=n;j+=i)//这里j表示i的倍数结果，每次加i相当于加一倍
            vis[j]=1;
    }
    return k;
}

这里给出1-100范围内的素数以供检验

范围 素数 (1,10] 2,3,5,7 (10,20] 11,13,17,19 (20,30] 23,29 (30,40] 31,37 (40,50] 41,43,47 (50,60] 53,59 (60,70] 61,67 (70,80] 71,73,79 (80,90] 83,89 (90,100] 97 3.2、埃氏筛 上面的构造方法，是对每个数字都进行倍增，但实际上这样的效率很低，造成了很多的重复。

比如说对2进行倍增之后，会对4,6,8,10,12,14,16,18,20,22,24,26,28,30等等进行标记

而轮到4的时候，就会对8,12,16,20,24,28,32等等进行倍增

可以发现这其中有大量的重复，这相当于重复标记了，并且这只是举了2和4的例子，后面还有更多的重复。而造成重复的根本原因就是后面进行倍增的数字，如4，是前面数字倍增后的结果。可以想到，4的倍数，8的倍数，必然是2的倍数，那么使用4,8进行倍增无疑是以不同的步长重复标记。4和8这类数字，都是已经被标记过的数字，换言之也就是合数。那么就是不应该对合数进行倍增，因为合数必然是某个素数的倍数(一定是某个素数的倍数吗？必然是，这是一个递归定义，必然终结于素数)。对合数进行倍增，就是在重复标记。

这里引入一个数学定理–唯一分解定理，也是算术基本定理

算术基本定理可表述为：任何一个大于 1 的自然数 N, 如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积—-唯一分解定义百度百科

因此合数的因子中一定有个素数，循环是从小到大的，那对最小的素数进行倍增之后，就不需要对其倍数结果进行倍增。（即对3进行倍增之后，就不在需要对6,9,12进行倍增）因此上面的算法，进行一点改进，就可以大大提升效率，而这种算法就是埃拉托斯特尼筛法，简称埃氏筛。

程序代码

时间复杂度O( N log(logN) )*

#include<stdio.h>
#include<string.h>//memset函数的头文件

//设定一个宏，定义数组大小
#define maxn 20010


int vis[maxn];//vis用来判断数字是否访问过
int prime[maxn];//prime用来存储筛选出来的素数

//埃氏素数筛函数
int Eratosthenes_sieve(int n)//这里用了英文全称，平时用sieve等命名就好
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)//从最小的素数2开始筛选，2以下就没必要筛选
    {
        if(vis[i]==0)//这个数是目前最小的，且未被访问过的
        {
            prime[k++]=i;//因此这个数是素数,存储起来
            for(j=2;i*j<=n;j++)//这里的改变就是把损坏放入if判断语句之内
                vis[i*j]=1;//只对素数进行倍增筛选，其他基本不变
        }
    }
    return k;//返回范围内素数的个数
}

void print(int k)//打印结果函数
{
    int i;
    for(i=0;i<k;i++)
    {
        printf("%5d ",prime[i]);//每个数字占5个宽度，右对齐，保持输出结果整洁
        if((i+1)%5==0)//每五个为一组换行
            printf("\n");
    }
    printf("\n\n");
}

int main()
{
    int n;
    int k;//保存返回的素数个数
    while(scanf("%d",&n)!=EOF)
    {
        k=Eratosthenes_sieve(n);
        if(k==0)
            printf("(1-%d]范围内没有素数\n",n);
        else
            printf("(1-%d]范围内的素数有:\n",n);
        print(k);
    }
}

3.3、优化方法一 再次观察上面的程序，会发现优化之后，仍然会有重复标记的情况出现，这是为什么呢？

仔细观察之后，发现是倍增的起点选择问题。上面的程序每次都是从2倍开始倍增，如果想要不重复标记，则需要从 i 倍开始倍增。

假设现在 i=b，如果从2倍开始倍增，将会标记b*2这个数，而这个数实际上在2倍增b倍的时候，就已经标记了。所以每次倍增应该从 i 开始，从 i^2开始标记。

这就相当于这张九九乘法表，如果没有从 ii 开始，从2倍开始，就会标记第2列到第9列中的所有内容。如果从 ii 开始，那标记的就是对角线部分+表格的上三角白色部分。这样就很明显看出，小小的一点改动，就节约了将近一半的计算。

程序代码

这里就不提时间复杂度了

//埃氏素数筛函数
int Eratosthenes_sieve(int n)
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            prime[k++]=i;
            for(j=i;i*j<=n;j++)//仅仅是这里，把j=2改为j=i
                vis[i*j]=1;
        }
    }
    return k;
}

3.4、优化方法二 这一步，让我们继续优化。

上一步，我们是优化到，只对素数进行倍增。结合朴素算法中的优化方法二：素数一定是奇数。我们是否可以再进行优化呢？

这里我们可以对上面的第一重循环进行优化，只判断奇数是否为素数，再进入第二重循环。

那么这种方法是否正确呢？先让我们看看如果这样做时候，会发生什么：

2以上的奇数(3,5,7,9等等)的倍增过程不受影响 2以上(包括2)的偶数，将不再倍增 第一点不影响算法的正确性，第二点，2以上的偶数，就是2的倍数，按照上面的优化过程，也不会倍增，这一点也不影响算法的正确性。而关于2的倍增，2的倍增都是偶数，并且全都不是素数，这一点进行一下预处理即可避免。因此我们可以进一步优化，只对奇数进行判断。

程序代码

这里也不提时间复杂度了

//埃氏素数筛函数
int Eratosthenes_sieve(int n)
{
    if(n<2)//之前不加上这句，是因为可以通过循环条件进行判定
        return 0;//现在前面有预处理，需要先判断
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    vis[2]=0;//这步可以省略，加上后方便理解
    prime[k++]=2;//这步很重要，不能省略，容易忘记
    for(i=3;i<=n;i+=2)//只对奇数判定，因此从3开始，步长为2
    {
        vis[i+1]=1;//把偶数的标记补上
        //这里存在大于n的风险，因此需要把数组开大一点
        //如果是i-1，则当n为偶数时，n的标记不能补上
        if(vis[i]==0)
        {
            prime[k++]=i;
            for(j=i;i*j<=n;j++)//这里把j=2改为j=i
                vis[i*j]=1;
        }
    }
    return k;
}

这里的优化并不是很明显，只是在循环中省略了判断偶数是否为素数这一过程

虽然针对时间要求高的题目有更好的算法去解决应对，但这种优化方式还是值得学习一下，一方面作为了解，成为知识储备，另一方面开拓思维。

3.5、优化方法三 埃氏筛的平方优化

让我们继续深入，看看有没有其他优化的方法

上面的朴素算法中，可以把O(n)的时间复杂度优化到O( sqrt(n) )。不需要对[2，n-1]中每个数字都判断是否为因子，只需要判断[2，sqrt(n) ]范围内即可，因为因子是成对出现，并且分布在sqrt(n)两侧的。因此只需要对一侧进行判断，如果这一侧的数字不是因子，那么另外一侧的数字也不是因子，这就可以说明这是素数。

那么这种方式是否也可以应用到埃氏筛中呢？答案是可以，不妨尝试证明一下

简单证明一下：一个范围内的数字分为素数和合数，合数有多个因子(至少3个)，且因子都分布在sqrt(n)两侧。如果左侧范围数字不是因子，那么由于因子是成对出现的，则右侧范围中也没有因子，因此可以说明这个数字是素数。回顾埃氏筛的过程，使用素数去倍增来筛选出合数。

一个合数x，必然有一个因子在[2，sqrt(x) ]范围内，当我们在这个范围内循环倍增时，必然会经过x的因子，那么在之后的倍增过程中，就得到合数x，并把合数x进行标记。（值得说明的一点是，这里的合数x是奇数，因为偶数的合数我们早就已经人为标记过了）

程序代码

时间复杂度暂时不提

//埃氏素数筛函数
int Eratosthenes_sieve(int n)
{
    if(n<2)
        return 0;
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    vis[2]=0;
    for(i=4;i<=n;i+=2)//这里把偶数全部标记为1，非素数
        vis[i]=1;

    for(i=3;i*i<=n;i+=2)//这里只是把 i<=n 改为 i*i<=n
    {
        if(vis[i]==0)//对素数进行倍增
        {
            for(j=i;i*j<=n;j++)//这里把j=2改为j=i
                vis[i*j]=1;
        }
    }

    //上面的循环，只循环到sqrt(n),因此要存储范围内的素数，需要重头遍历一遍
    prime[k++]=2;
    for(i=3;i<=n;i+=2)//只遍历奇数
    {
        if(vis[i]==0)
            prime[k++]=i;
    }
    return k;//返回素数的个数
}

这个程序后面补了一个循环，和之前的程序相比，效率似乎反而降低了。之前的程序，在一遍循环中完成标记和存储两个任务，而这个程序需要三个循环。

我没有测试过不同程序的具体耗时，无法给出一个准确的比较结果。但这个程序适合于只标记，不存储的情况，这样就可以少一个循环。另外这个程序的效率还是高的，时间主要节约在第二层循环中：其他程序，对每个素数都要进行倍增，而这个程序只对sqrt(n)内的素数进行倍增，当数据量越大，则两者之间素数的个数就差的越大，继而倍增的次数就相差越大。就比如说n=20的时候，前者需要对2,3,5,7,11,13,17,19倍增，而后者只需要对2,3进行倍增。n=100时差距就更大了，前者需要对25个素数进行倍增，后者只需要对2,3,5,7进行倍增。

4、素数筛-欧拉筛 埃氏筛有一个问题，就是一个数字可能会被重复筛除。比如说12，可能在2的时候被筛除，可能在6的时候被筛除。即使进行了上面的优化(只对素数进行倍增)，也还是会被3筛除。这里只是举一个例子，当一个合数数字越大，其中的素因子越多的时候，则重复被筛除的次数就越多。

欧拉筛就是要解决这个问题，保证每个合数只被筛选一次，从而提高效率和运行速度，那么怎么做呢？

根据唯一分解定理可知，每个合数都有一个最小素因子。而欧拉筛的基本思想是，让每个合数被其自身的最小素因子筛选，而不会被重复筛选。欧拉筛的框架和埃氏筛大致相同，区别点在于第二层循环对倍增过程的操作。

埃氏筛是，只要是素数就进行倍增。而欧拉筛是用当前遍历到的数字i，去乘以已经在素数表中的素数。

首先，这样就保证了是以素数进行倍增，相较于使用任何数字进行倍增的情况，是已经优化过了。比如说此时i=6，前面有素数2,3,5。在欧拉筛中就是用2,3,5去乘以6，进行倍增筛除。因为 i 是从小到大进行循环，会乘以前面的每一个素数，这就保证了每个素数的倍数都不会被错过。并且每个素数的倍增过程都是从平方开始，就和前面埃氏筛优化方法一种一样，可以有效避免重复。

举例说明：现在 i 循环到6，前面有素数2,3,5，这三个素数，都是从22，33，55开始倍增的，不会出现23，3*2的情况同时出现。

那么至于怎么保证每个合数只被标记一次呢？这里我们先看核心代码

//欧拉筛函数
int Euler_sieve(int n)
{
    int i,j,k;
    k=0;//保存素数的个数
    memset(vis,0,sizeof(int)*maxn);//初始化数组
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)//i是素数，则存起来
            prime[k++]=i;
        for(j=0;j<k;j++)//进行倍增，用i去乘以i之前(包括i)的素数
        {
            if(i*prime[j]>n)//倍增结果超出范围，退出
                break;

            vis[ i*prime[j] ]=1;//将倍增结果进行标记

            if(i%prime[j]==0)//i是前面某个素数的倍数时，也需要退出
                break;
        }
    }
    return k;
}

代码中，最关键是这条语句

if(i%prime[j]==0)
    break;

这条语句的加入，保证了每个合数只会被筛除一次，不会被重复筛除。那么为什么？

当 i 可以整除素数表中某个素数时，那么 i 就不需要在往后乘以其他素数了，因此往后乘以得到的结果，会以另外一种方式得到。

用公式解释就是

当 i%prime[j]==0时，iprime[j+1]的结果，可以通过另外一种方式得到，比如说 xprime[j]，即xprime[j]=iprime[j+1]

i%prime[j]==0 说明prime[j]是i的一个素因子，并且是最小的素因子(因为是最早接触的素因子)，所以i可以表示为a*prime[j]的形式

那么iprime[j+1]即等于aprime[j]prime[j+1]的，所以iprime[j+1]的结果，也是prime[j]的倍数，当i往后继续循环到x的时候，就会有x*prime[j]出现，就把之前的结果给补回来了。

prime[j+1]是这种结果，往后的j+2,j+3等等也是类似的结果，因此这里就可以退出循环，等到i循环到x的时候，再把这个合数结果筛除。

这里合数到了prime[i]就退出了，因此后面的素数没有倍增的机会，即这个合数不会被其他素因子倍增到。(不会出现26=34=12等重复标记的情况出现)

因此每个合数只被其最小的素因子筛除，不会被其他素因子筛除，因此欧拉筛中每个合数只会被筛除一次，不会被重复筛除。

举例说明就是

比如i=12，此时素数数组中有素数2,3,5,7,11

2*12=24，把24筛除了，但是判定12可以整除2，2是12的最小素因子(是因子，且是素数因子)，此时循环退出。

为什么呢？

因为123=36这个结果可以通过12的最小素因子2，以其他方式得到。36这个结果，当x=18时可以通过182得到。同样的，后面的素数12得到结果，也可以通过另外的x与2相乘得到。比如125=60，可以通过30*2得到

上面使用公式进行了解释，这里再说明一下，2是12的最小素因子，12可以被2整除，那么12乘以其他的素数得到的结果，也同样可以被2整除，得到的商就是那个x。因此这里就不再第二层循环中往后乘，而是跳出第二层循环，进入第一层循环。等到第一层循环中循环到了合适的i=x时，就可以复现此时的结果。因此这个合数并不会被忽略，而只是筛除的过程滞后了。

这样的滞后操作，保证了每一个合数，只被筛除一次，不会被重复筛除。这种筛除方式，就是欧拉筛算法最前面提到的，使用最小素因子筛除。

6、区间筛 这里挖个坑，过段时间补上

6、素数筛总结 这里给出一点编程小技巧：

如果是用作标记，可以选择用更小的数据类型进行存储，比如说short，bool类型。甚至经过巧妙设计之后，可以使用 位 来标记 循环中尽量不要出现表达式，可在外面用变量存储表达式的值，再放入循环中。避免每循环一次，都要重新计算一次 求素数的几种方法：

判断单个数字是否为素数 试除法（穷举法） 优化方法一：范围缩小到n/2，原因是合数因子范围为[2，n/2] 优化方法二：使用奇偶数性质优化，原因是素数是奇数，奇数不能被2的整数倍(偶数)整除 优化方法三：上面两种方法结合 优化到sqrt(n)的试除法，原因是因子成对且分布在sqrt(n)两侧，检测一侧即可 优化方法一：使用奇偶性质优化，原因不重复 筛选区间范围内的素数 埃氏筛 引入中，利用任何数字的倍数都不是素数的性质 埃氏筛，只对素数进行倍增，利用唯一分解定理，合数必然可以分解出素因子 优化方法一：倍增从 i 开始 优化方法二：只对奇数进行素数判定，以为素数一定是奇数 优化方法三：开平方优化，同样是因为数字的因子成对出现且分布在sqrt(n)两侧 欧拉筛 1. 这里有多种优化方法，有的甚至是多种优化方法复合使用。但在复合使用前，需要先判断一下这样做是否会影响程序的正确性。 ————————————————

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/Yuki_fx/article/details/115103663