本文主要是介绍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)的条件即可
这篇关于c++浅析素数原理和埃拉托斯特尼筛法(埃筛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!