00:02
这节课讲阿泰竞赛之前讲了埃塞和阿拉塞都是批量找叔叔的，而阿泰基赛同样是批量找叔叔。比如1~100之间的所有数数。嗯，阿特金山的时间复杂度，这个网上的资料不太一样，我个人倾向于limit米特这个时间复杂度。那在进3的算法步骤是这这几步，首先是创建一个数组，这个数组其实就是标记表。嗯，全部标记为po，意思就是全部都是合数，而之前讲的S和标记表全是质数。这是一个。区别。另另外一个区别就就是最次翻转。这个S。
01:01
嗯，爱赛和拉赛都是标记，为何处？这，这是另外一个区别。我们直接看这个。第一步，创建一个数组，这个我们看一下代码。这个。就是出事完了一个宿主。然后第二步将2、三标记为除数。第二步，将二、三标记为数数。第三步，第三步和第4步融合起来。然后第三步，N=4X方加Y平方。XY是什么意思啊，我们看一下。XY都是1到根号里米的，也就是说XY这都是一个循环变量。从这里也可以看出，这个时间复杂度就是厘米特了。
02:07
嗯，看第一个条件。N=4X平方加Y平方。嗯，这个地方，这个地方就Y平方，然后判断条件N与除12等于或者N与除以12=5。这个这个地方等于42=1=42=5，没条件的就直接翻转。然后N=3X方加Y平方。这第二步。3+Y平方。然后N余除以12=7。等于余数12=7。无条件的翻转。第3步。N=3X方加减Y平方。
03:05
然后满足X>Y，就注意X一定要大于Y呢。这个地方有个X>Y，然后还有一个条件，A于除12=11。N÷12=11。然后符合条件的直接翻转。然后进行下一次便利。这个Y全部编完成过后，就是进行第5步。这个第5步也是非常重要的。从5开始，便利。如果当前筛子对应的是数数。然后就需要将。X的平方以及所谓的倍数都标记为合数。我们看一下代码。
04:00
这个地方2从5开始。如果筛子的当前位置是数数，然后就标记它的平方。L的平方，然后。后面长也是2的平方，嗯，全部标记为合数。第5步完成过后，然后就直接便利这个筛子，然后打印出输入。代码也是这样写的。我们看看一下举例。1~100的之间的数，首先标记2和3。二三，然后条件。为什么？这周围有一个五呢。这是因为4X版叫外屏吗？X=Y=N就等于5。这个5余数12就等于5符合条件，符合条件就5这个位置翻转。
05:07
翻过后就是235。而第二个条件。X等于，Y等于，这个时候N=4。N=4，余数12≠7的，所以不会翻转。所以还是二三第三个。3X平方减Y平方X=Y=N就等于2。X>Y，这个时候是B等于。X.等于1 Y是等于的，所以这个条件不满足，所以还是235。然后进行下一个下一个便利，也就是X=1。Y=2。X=Y=2就是。4+4=8，则。
06:01
二八不，不符合这两个条件，所以还是235。这个。S=1。3+4=7。N余数12=7所，所以就是2357了。第三个3X方减Y平方，这个X它是X=Y=2，所以X小于不符合条件，所以还是2357，后面就一直便利。我们可以看到这这之前呢，这是。一直数字是一直增加的，有没有减少的情况，根据翻转的。情况，他肯定是有减少的情况的。我们可以看到之间这个地方就已经发现有减少的情况了。
07:00
然后我们再看一下后面还有没有。看这个地方也也有减减少的情况。我们再看一下后边。后面好像都是不变的。就是最后和这一步是什么意思呢？主要是去除了平方向。嗯，注意这个地方都那个25，呃，25它就是5的平方。所以这。这个地方。又少了一个25，这这也是最终的结果。这个与S3的区别。这个首先标记表里面全是合数，而S3的初始全是数数。
08:09
第二个区别是。嗯，标记表里面的元素是翻转，而S里面标记全是合数。这这两个区别非常重要的，请大家记住。
我来说两句