c语言求素数的代码 c语言求素数

今天这篇是算法与数据结构专题的第23篇文章，我们继续数论相关的算法，来看看大名鼎鼎的埃式筛法。
我们都知道在数学领域，素数非常重要，有海量的公式和研究关于素数，比如那个非常著名至今没有人解出来的哥德巴赫猜想。和数学领域一样，素数在信息领域也非常重要，有着大量的应用。举个简单的例子，很多安全加密算法也是利用的质数。我们想要利用素数去进行各种计算之前，总是要先找到素数。所以这就有了一个最简单也最不简单的问题，我们怎么样来寻找素数呢？

判断素数

寻找素数最朴素的方法当然是一个一个遍历，我们依次遍历每一个数，然后分别判断是否是素数。所以问题的核心又回到了判断素数上，那么怎么判断一个数是不是素数呢？
素数的性质只有一个，就是只有1和它本身这两个因数，我们要判断素数也只能利用这个性质。所以可以想到，假如我们要判断n是否是素数，可以从2开始遍历到n-1，如果这n-1个数都不能整除n，那么说明n就是素数。这个我没记错在C语言的练习题当中出现过，总之非常简单，可以说是最简单的算法了。
def is_prime(n):for i in range(2, n):if n % i == 0:return Falsereturn n != 1

显然，这个算法是可以优化的，比如当n是偶数的时候，我们根本不需要循环，除了2以外的偶数一定是合数。再比如，我们循环的上界其实也没有必要到n-1，到根号n就可以了。因为因数如果存在一定是成对出现的，如果存在小于根号n的因数，那么n除以它一定大于根号n 。
这个改进也很简单，稍作改动即可：
def is_prime(n):if n % 2 == 0 and n != 2:return Falsefor i in range(3, int(math.sqrt(n) + 1)):if n % i == 0:return Falsereturn n != 1

这样我们把O(n)的算法优化到了O(\sqrt n)也算是有了很大的改进了，但是还没有结束，我们还可以继续优化。数学上有一个定理，只有形如6n-1和6n+1的自然数可能是素数，这里的n是大于等于1的整数。
这个定理乍一看好像很高级，但其实很简单，因为所有自然数都可以写成6n,6n+1,6n+2,6n+3,6n+4,6n+5这6种，其中6n,6n+2,6n+4是偶数，一定不是素数。6n+3可以写成3(2n+1)，显然也不是素数，所以只有可能6n+1和6n+5可能是素数。6n+5等价于6n-1，所以我们一般写成6n-1和6n+1 。
利用这个定理，我们的代码可以进一步优化：
def is_prime(n):if n % 6 not in (1, 5) and n not in (2, 3):return Falsefor i in range(3, int(math.sqrt(n) + 1)):if n % i == 0:return Falsereturn n != 1

虽然这样已经很快了，但仍然不是最优的，尤其是当我们需要寻找大量素数的时候，仍会消耗大量的时间。那么有没有什么办法可以批量查找素数呢？
有，这个方法叫做埃拉托斯特尼算法。这个名字念起来非常拗口，这是一个古希腊的名字。此人是个古希腊的大牛，是大名鼎鼎的阿基米德的好友。他虽然没有阿基米德那么出名，但是也非常非常厉害，在数学、天文学、地理学、文学、历史学等多个领域都有建树。并且还自创方法测量了地球直径、地月距离、地日距离以及黄赤交角等诸多数值。要知道他生活的年代是两千五百多年前，那时候中国还是春秋战国时期，可以想见此人有多厉害。

埃式筛法

我们今天要介绍的埃拉托斯特尼算法就是他发明的用来筛选素数的方法，为了方便我们一般简称为埃式筛法或者筛法。埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。
举个例子，比如我们要筛选出100以内的所有素数，我们知道2是最小的素数，我们先用2可以筛掉所有的偶数。然后往后遍历到3，3是被2筛剩下的第一个数，也是素数，我们再用3去筛除所有能被3整除的数。筛完之后我们继续往后遍历，第一个遇到的数是7，所以7也是素数，我们再重复以上的过程，直到遍历结束为止。结束的时候，我们就获得了100以内的所有素数。
如果还不太明白，可以看下下面这张动图，非常清楚地还原了这整个过程。

和我们的预期一样，获得了小于100的所有素数。我们来分析一下筛法的复杂度，从代码当中我们可以看到，我们一共有了两层循环，最外面一层循环固定是遍历n次。而里面的这一层循环遍历的次数一直在变化，并且它的运算次数和素数的大小相关，看起来似乎不太方便计算。实际上是可以的，根据素数分布定理以及一系列复杂的运算（相信我，你们不会感兴趣的），我们是可以得出筛法的复杂度是O(nlnln n) 。

c语言求素数的代码 c语言求素数

推荐阅读

梦见牙齿掉了并吐一把是什么意思梦见牙齿掉了并吐一把有什么预兆

梦见小老鼠是什么意思梦见小老鼠有什么预兆

camtl00是什么型号

2019春夏女装面料采购指南 2022年最流行夏装面料

脏辫可以自己打理吗

熬夜易致皮肤受损抵抗力下降通过膳食调整得到补救

咋得才能把图片导入cad

全城7怎么样

吉林修正和柳河长隆是一家吗

什么的因数只有一个什么的因数只有一个呢