2.10.素性检验之分段筛segmented sieve原创

这节课讲分段塞，分段塞的原理跟S塞的一样，不同点是分段塞节算的空间S4塞的空间复杂度深。分段上的空间复杂度是根号N。原因是分段在把标记表的范围分成了根号N段，每段根号N的长度，因此空间复杂度是√2关于时间复杂度。N乘以诺恩根号，这是网上资料写的，但我个人认为应该跟S3的一样，都是N×no恩。勒个勒个具体算法步骤直接看举例。1~100。左闭右开，意思是不包含1000之间的左右数数。首先求√101。嗯，直接看代码怎么写的。这个就是求。

根号N大，当然最后加了个1。所以根号√101=10 10+1=11。然后求出1~11之间的所以次数，也就是2357。因为它是不包含11的，所以这个11并没有写进来。嗯，我们看一下。这个是求数数的，这个是怎么求的，这是这个是根据S3求出来的。2357就是这一步求出来的。然后下面。然后去先求左边界，然后再求右边键。左边界开始。Limit.右边键还200cm。这这个求出来啊。

这个肉肯定是小于N的。这个还等于是肯定。他也是小圆的，所以这一步不会执行。这是标记表。标记表的长度是根号。然后下面就便利。这个prime prime就是指这个2357。这个这是是在这里面求出来的。注意注意这个。然后我就。这个是什么意思，这个事情。据据你。左边键。

嗯，最小的合数。这个怎么理解这个。从2357开始编的。刚开始PN是等于2的，2NO它是等于11的。然后11+2-1。然后除以2，然后再乘以2，就算出来就等于12，而12就是距离11最近的合数。然后合数，然后标记一下，那个就直接标记成合数了。注，注意这个地方。因为之前的SJ肯定是等于P×P的。嗯，小于。小于P×P的就不需要再次标记了。然后这这个和P×P，求一个最大值。

然后这一步循环完了，然后就开始下一个速速的循环。然后。如果这个双重循环执行完了，那么直接的打印。也就是把把这个给打印出来，十一，十三，十七，十九。嗯，下一步。No等于加等于厘米塔。也就是已经变成了22。它也是加上厘米的，就是22+11，嗯，就等于33了。然后。那就就进行下一次循环。也就是。就是这个循环。然后再打印之间的处处。注注意注意这这个地方。

这个标记这个数数数prime，它始终是2357，这个十一，十三，十七，十九后面是用不到的。然后这这是大体的过程，我们直接看一下运行结果。我们可以看到。这正是1~100之间的数数。