2.6.素性检验之普里查德筛sieve of pritchard原创

这节课讲普查德赛，普查德塞跟之前讲的S赛和拉塞一样，都是量走数数的。比如举例中的。1~401，就这里面的所有数数，时间、复杂度跟S3的一样，都是N×log log个N，不过运行速度是比不上S塞的。嗯，普利茶的菜跟S31样，也有一个标记表。包括区别是埃塞的标记表初始全是数数，而普利查德塞的全是合数，然后标记的时候就把合数变成数数。但是有有少数情况会将叔叔重新标记为火数。首先是将1标记为诉讼。嗯，算法步骤就直接看举例1~401。

嗯，这一块是一个循环，下面这一块也是一个循环，这一块也是一个循环。这个我们看这个prime prime是数数的意思，我们看一下最后循环到什么时候。我们可以看到最后等于19。也就是说这个plan等于二三五七十一，13等等一直到19，为什么到19就就停，这这是因为。这个四百零。4000开一个根号等于20。所以这个质数它是小于20的。这个循环次数已经决定下来了。我们再看后面这两个参数。嗯，首先看N米塔是263是210。

这个2。乘以3=66×5。等于30。30×7=210。嗯，这刚好就是数数的阶阶层。而step仍是。初始为1，然后变成二六三十。210这也是一个数数数的阶层。只只是区别跟里面的。刚刚出了一下位，出数1，然后N=2。下面的那都是一样的。嗯。这下面的M1M2是是什么意思啊，这这个地方我们就直接看一下代码。

嗯，首先刚开始members。这个就是标记表。标记为全火数，而。首先将1标记为数数。也就是这个。然后这个是初始值，也就是说。这这个值已经固定下来了。然后这个是收集数的。首先就是进入循环。循环里面这个S<limit。这肯定是小鱼了。然后进行。然后就做一些操作。操作之前是1，也就是这还其实还是打赢了members。然后经过处理过后变成了2。

其其实M1和M2的都是。都是，也就是标记表，这个打印的时候只打印数数。然后M1边长M2，也就是。就多了一个数字，这个数字是等怎么的多起来的，其实就是1+1个步长。就变成了2。N22加不长。等于3，这个3已经超出范围了，所以M2就就等于1和2。这个算法里面也是N加一个，N加等于一个不长。这个过程就是M1变长M2的过程。然后过程变，变完过后。然后就看delete。

Delete,它是把2给删除了。也就是说，第2项。因为因为你循环了12，所以就算错了2。所以最后M3就等于1了。我看代码。这是一个酸出之前，然后。这段代码就是双创的操作。然后算出个就是M3。嗯，俺们咱。生日。最后最后变成了M3，然后再进行下一下一轮的循环。现在喜欢prime=3。我们看一下代码。注意。本来是等于2的，然后强制设置为等于3的。然后部长。

An unli.肯定也有变化的。这个M1等于之前的M3。然后M2是这这怎么算算出来的。主要是看布场。不长等于2，所以1+2=3。嗯，3他也也也可以参与进来，3+2=5。然后5+2。等于7已经超过6的范围了，所以7不不会记录下来。嗯，这。所以又回到上面这个步骤了。这周我就不看代码了。然后DELETE3，也就是有3到手，我就我需要把。标记表里面的3个删掉。

然后进行，所以最后就变成了1和5。嗯，下一轮就是5。嗯，就。也就是这个地方。向变成5了，C=6。呃，M1对应上面的M3，也就是1和5。这个这个地方也是1和5，然后。然后又，又是伦加了。1+6=7。然后5+6。等于11。然后七一和11虽然是新加进来的，但也未参与这个的加法。7+6=13。11+6=17。这两个也是新加进来的。然后13+6=19。

17+6=23，这两个也是新加进来的。然后。19+6=25 23+6=29。然后M2就变成这个样子。嗯，然后又有一个删除的操作，这个删除的操作是将。这里面的数数数标记，又重新标记为何数。嗯，看一下代码。M3这个地方。就是就是这段代码。这个30号只有5号25。所以这就剩剩下的就是一七十一，十三等等。

然后进行下一轮循环，下一轮循环不等于7了。然后C=30N limit=210。然后M1对应之前的M3。然后M2就。1+1+30。这个。这段是直接抄下来。然后1+30=31。7+30=37。11+30。等于41。13+30=43，这个后面都是依次加进来。嗯，一直加到N小。如如果大于N厘米的就退出循环，那就不用加了。

然后加完过后又需要减。如何减呢？这个时候注意这个prime=7的，所以需要删除7大倍数。这个7道被作有这么多。然后把7大倍数给算出完了，然后就变成。这个样子，这可能会变少的，然后下面等于11的时候。嗯，也是同样的操作。嗯，然后下一步等于13，注，注意13这个地方，这个steps=401，也是等于401。他们没有M1和M2了，这这是什么意思啊？也就是说我们这个M1变成M2，这是一个轮加的过程。这个。数数的个数肯定会会变多的。

呃，这个steps等于等于limit的时候。这个就。这个标记表就不会变多了，然后只只只有变少的过程。我们看一下代码。也就是说，S小于厘米特的时候，这个1才会变成M。然后。如果相等的情况，那就那只要是删除了。Later.这个delete删除13的倍数。然后这个就删除17的倍数。然后下面的循环就算出19的倍数。然后最后剩下的就是。最终形态。最终形态数数的话，就从这个地方开始。

23~401。嗯，这个数数已经全部出来了。嗯，但是少了一个2357等等，这个这个地方。You prime.已经收集到2357，一直到19。这这两个合并起来就是需要到求到数数。我们看一下运行结果。这个运行结果就是1~401之间的数数。全部都已经求出来了。这个普利查德赛的思想，其实就是伦嫁的过程。