欧拉筛法原理C语言,素数筛法

素数筛

自古以来，素数就是一个有众多人研究的东西，而素数筛也是这些研究成果中的一个

素数筛是用来快速生成一个素数表的东西，比起生成素数的幼稚算法及其优化的方法，素数筛的速度更快，但是也常常会出现很多奇奇怪怪的bug，以后再说。

今天先介绍一下欧拉筛和埃氏筛

这两种筛法是素数筛里最常见的

1.埃氏筛

原理：

​ 素数的倍数一定不是素数

思路：

​ 我们先生成一个数组vis，给上面每一个位置都初始化为✔，然后将0和1位置变为✘，因为0和1一定不是素数

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✔

✔

✔

✔

✔

✔

✔

​ 然后我们从第二格开始，因为2是素数，所以我们把4,6,8,10……都变为✘，如下表：

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✘

✔

✘

✔

✘

✔

✘

​ 同样的，我们来看看第三个，因为3是素数，所以我们把6,9,12……都变为✘，如下表：

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✘

✔

✘

✔

✘

✘

✘

​ 然后我们再来看看第四格，第四格已经被标记为了✘，所以我们跳过第四格，经过多次这样操作后，vis数组中便筛出了某一个范围内的所有素数

​ 我们再通过一次for循环遍历，找出所有标记为✔的下标，便是所求素数了

实现代码：

​ 实现代码可能和以上描述有些许出入，但是大体思路没有问题 : )

const int N=1e7+1;

int prime[N],cnt=0;

bool vis[N];//使用bool型，节省空间；

void get_prime(){

memset(vis,true,sizeof(vis));

vis[0]=vis[1]=0;

for (int i=2;i

if (vis[i]){

prime[++cnt]=i;

for (int j=2;j*i

b[i*j]=false;

}

}

}

​ 该算法的时间复杂度为O(nlglgn)≈O(n)，是一种趋近与线性的算法，速度较快，能够应付大多树的题目，那有没有更快的呢？

当然有！下面让我来介绍一个更快的算法：

2.欧拉筛(线性筛)

​ 在讲欧拉筛的时候，我们先回顾一下埃氏筛

​ 埃氏筛会对素数的所有倍数进行标记，这也导致了一个比较大的问题，例如：6，因为他是3的倍数，同时也是2的倍数，所以在埃氏筛中，6被删掉了两次，而在比较大的合数中，更是被删掉了更多次(每有一个素因子就会被删掉一次)，这也导致了太多系统资源的浪费，同时也导致了时间的延长，更有可能会让程序的运算时间+1s，这是很危险的，所以我们要想办法来解决这个问题。

然后，欧拉筛诞生了。

原理：

​ 任意一个合数都能由几个素数乘得

思路：

​ 我们先生成一个数组vis，给上面每一个位置都初始化为✔，然后将0和1位置变为✘，因为0和1一定不是素数

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✔

✔

✔

✔

✔

✔

✔

​ 接下来，我们来看看2，这次，我不再将4,6,8,10……标记为✘了，我只将4标记为✘(4=2x2)

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✘

✔

✔

✔

✔

✘

✔

​ 然后我们再来分析3，与上一步相同，我将6和9标记为✘(6=3x2,9=3x3)

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✘

✔

✘

✔

✘

✘

✔

​ 然后再来看看4，尽管4已经被标记为了✘。我们将8,12标记为✘(8=4x2,12=4x3)

0

1

2

3

4

5

6

7

8

9

10

✘

✘

✔

✔

✘

✔

✘

✔

✘

✘

✔

​ 接下来看5，我们将10,15标记为✘……

​ 通过观察，我们发现，被标记的位置都是当前位置的数和该位置之前的素数的乘积，而每一个位置都只被标记了一次，节省了系统资源，时间-1s

代码实现：

const int N=1e7+1;

bool prime[N];

int cnt=0,vis[];

int init(){

memset(vis,true,sizeof(vis));

vis[0]=vis[1]=0;

for (int i=2;i

if (vis[i]) prime[++cnt]=i;

for (int j=1;j<=cnt&&prime[j]*i

vis[prime[j]*i]=0;

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

}

}

}

该算法比埃氏筛速度更快，但是一般的题目中，都推荐直接使用埃氏筛

番外个体：素数的判断

判断素数？这么简单的东西，刚刚学C++新手都会，这还用教？

是的，判断素数的幼稚算法确实简单，但是因为其时间复杂度实在太高O(n^2)，在面对1e6这种数量级的数字时便显得软弱无力了，那么这种大数字的素数该如何判断呢？

当然是要结合素数筛法和幼稚算法啦

首先，我们利用素数筛法筛出一定数量的素数，例如我们判断1e6这种怪物的时候，就生成1e3大小的素数集合prime，接下来要做的事，就是开始枚举，但是枚举也是有技巧的

我们只需要看这个数是不是素数的倍数，便可以知道这个数是不是素数

代码如下：

int isprime(int number){

bool flag=false;

for (int i=1;i<=sqrt(n);i++)

if (number%prime[i]==0){

flag=true;

break;

}

if (n==1) flag=1;//对1进行特判

return flag;

}