2.3.素性检验之埃氏筛sieve of eratosthenes原创

这节课讲X43之前讲的次数法是判断一个数是否是数数，而X43是求某个范围里面的数数，比如1~100之间的输出。嗯，爱斯赛跟传统的思想略微一点区别。传统的思想是依次便利，然后就能依次判断某个数是否是数数，而埃斯塞它是判断何数。假设1~100之间的数都是数数，然后1肯定是既不是数数，也不是合数，然后从二二开始变利。然后2肯定是数数，然后2的倍数就是合数。也就是四六八十，十二十四等等。然后2遍历完了，然后就是便利3。

三三肯定是数数。嗯，然后从9。锐是P的平方。这个3是从，然后3的倍数就是9。六六月虽然也是3的倍数，但不，不能从6开始。然后从9开始，九十、二十五、十八等等，这些都是合数。然后下一个数就是4 4本身是合数，所以就不需要找它的倍数了。5。嗯，五五，你不能从十，十五开始，必须从5的平方开始，也就是25。三十，三十五，四十等等。然后下一下一个就是6。6。6它是合数，所以不不需要变零，然后再下一个数字就是7 7，不不能从14、21等等开始，只能从7的平方49开始，也就是49 56 63等等。

然后下一个就是8。当时合作。不不不需要变量99也是合数14合数11是数数，但是11已经超过了√100的范围，也就是10。所以也不需要便利，也就是说这之后的都都不需要便利了。嗯，我们直接看看一张Excel表，这是1~100之间的数字。假设，首先是假设所有的树都是树树。然后1它是一个特例，所以我们直接标记为合数。

红色的就就说合作。然后从2开始编离2 2它是支柱，所以我们不需要标红。然后标记2的倍数，那那都是合数，2的倍数有哪些呢？那自然就是这些数。这些都不红。然后2遍利完成了，然后从3开始。三明香也是质数。嗯，然后标记3的倍数，三的倍数是从肯定是从9开始，不不是从6开始。我们可以看到，New已经被标记过了。N99是3的倍数，然后标记一下，92已经被标记过了。是。

18。21。244。27。30。343。36。39。四十二，四十五。嗯，48。54。57。60。63。66。69。七十二，七十五。七十八，八十一。84。87。就是。943。九十六，九十九。

这三个倍数已经标记完了，然后下一个就是4 4已经是合数，所以不不需要标记4的倍数了。然后再下一个就是我。五只只能从25开始。不，不能从10开始，因为。因为因为25字之内的5的倍数已经被标记过了，所以不不用管，然后我们只标记5的平方，也就是25。开始下一个是30。35。40已经被标记过了45。50，这这些都都被标标记过了55。60。65。

其实。75被标记过了80，也被标记了85。标记一下。就是标记一下。90已经被标记过了，就是我。然后我被标记完了。嗯，下下一个就是六，六是合数。嗯，所以不，不用标记6的倍数。然后下一个就是7。7。从49开始。治疗。四十九七八五十六。已经被标记了79643。被标记过70。77。

嗯，71标记，然后77+7等于八四十四。84+7=91。标记一下。然后已经九九十一加七九十八。这个7的已经被标记完了。然后下一个就是八九十。嗯，这些都是偶数，所以不需要标记它们的倍数。然后再下一步就是11 11肯定是数数，但是10 11的平方已经超过100了，所以就不用管了，也就是说之后的数字我们都不需要管了。嗯，这个S3的思思就是这样的。嗯，我们这这个地方1~100，所以我们只需要看2357的倍数。

嗯，我们可以，我们看到这个变离子只是变离到2 2到根号N之间，为什么这个时间复杂的还是N乘以那个那个N呢。为什么不是这个地方，为什么不是√2呢？这是这是因为这个我们变变利了2357，这个后面的数数都已经出来了，但是我们还还要看每个数。我们需要收集哪些书是输出这个收集的过过程，这个都需要全部遍历一次。所以这个时间复杂度肯定是N×log根了。嗯，这个优点，这个优点的话，它是非常简单直观，这个非常符合自然智慧，智慧缺点是有重复标记的情况。

比如说比如说这个红色的30，这个二三五里面。都重新标记了。我们就直接我们看一下代码。嗯，代码代码是来自这个地址。嗯，我们就直接看代码吧。首先是。来一个宿主是。0~100。N=100，也就是0~100之间的数。这个数组是有101的长度。然后就假设所谓的树都是树树。

然后从2到。根号N之间变低。从注意是从2~2~10之间便利。如，如果，如果当前的数是负数，那么我们就开始标记为合数。也就是从P的平方开始，就注意这个是这个地方是P的平方，并不是2×P。如果是2×P的话，这个时间复杂度就已经变了。然后P的平方，然后P的平方加P。然后再加2批，然后依次电力标记为合数，然后。然后下一步就是P=3 3依然是数数。然后再再来一次标记为合数，再下一步P=4。

4那个衣服，这个4已经被标记过了，所以这个衣服肯定是为所以。直接下一次循环，一直循环到P=10的时候。然后就退出了。整个循环。但是。这这个地方的时间复杂度其实。表面上看起来是跟根号N植入，植入外侧循环是根号N。但是我们还有一个收集的过程，然后从N到N之间收集，这这是一个变的一个过程。请。所以时间复杂度一定是N乘以多少。我们直接看一下运行结果。我们可以看到这个243是二三五七十一十三的吗。

跟之前讲的四出版里面的是一样的。