c++浅析素数原理和埃拉托斯特尼筛法(埃筛)

c++浅析素数原理和埃拉托斯特尼筛法(埃筛)

（以下图片来自wikipedia）

素数定理

我们先来看一个问题，对于一个不超过n的正整数，其中有多少是素数：

这就需要用到一个老朋友

我们高中经常见到的一个函数

其中  表示不超过x的素数的个数

上述函数表示不超过素数的数量可以用x/lnx来拟合

那么对于100个数中，就能大概计算出素数的个数约为22个，实际为25个

这样在做题时就可以大约估计出区间内素数的个数

Eratosthenes筛法

又称埃筛，是判断素数最为常见的一种筛法

所谓“筛”，是一种形象化的描述，我们设置的条件就如筛子上的孔，筛掉的杂质就是我们不需要的

合数，留下来的精品就是我们需要的素数

一个好的“筛子”，空的大小要合理，排布要准确，如果一个一个筛去，便会十分费力

所以我们要优化孔，是其筛的效率更高

对于每一个素数p，筛掉p的倍数，当筛完一轮之后（见文章开头的图），剩下的便是素数

下面给出代码

//to find the prime among 1 and nfor(int i = 2; i <= n; i ++){for(int j = i * 2; j <= n; j+= i) prime[j] = false;}

对于第二行循环的条件，我们解释一下

其中先令j是i = 2的2倍（因为2是素数），每次都递增i的一倍，即j = 4 -> j = 6 -> j = 8...

每次i的递增，当i等于3时，j起始为6，然后为9...

当i = 4时，会发现4已经被筛掉了，这里可以引出欧拉筛，一种更为巧妙的筛法，但在这里先不做介绍

...

以此类推，就如同开头的图一样，把质数的倍数全部筛掉了！

多么简单而又高效的一种算法！

时间复杂度分析

我们对程序的时间复杂度进行一次分析

对于每一个i值，内部循环的次数越是（想一想为什么，很简单！）

即当i=2时，即为n/2

对于多次,并求和相加，便得到

 想一想这像什么？有没有想到把n做为因子提出来

没错，就是泰勒展开式

所以其复杂度为 O(nlogn) 

这样的运行效率已经很高了，为了更高，我们可以降低我们区间的范围

对于一个自然数来说，只要通过在的范围内的素数，就能筛掉n范围内的所有合数

为什么呢？

很简单，我们先来看一个数 72

他的约数有(1,72), (2, 36), (3, 24), (4, 18), (6,12), (9, 8)

会发现，72的平方根约为8.4, 而每个约数对里必有一个小于8.4的数，所以只要能判定

的范围内的素数，就能筛掉n范围内的所有合数

所以只需限定一个sqrt(n)的条件即可