筛选法工作原理

筛选法（Sieve Method）是一种用于素数筛选的算法。它的工作原理是通过逐步排除法来确定一定范围内的素数。

该算法的基本思想是从2开始，将所有小于给定范围的数标记为素数。然后，从2开始，将它的倍数标记为合数。然后，继续选择下一个未标记的数作为下一个素数，并将它的倍数标记为合数。这个过程一直持续，直到选取的素数的平方大于给定范围，即可确定所有小于给定范围的素数。

具体来说，对于一个给定范围N，首先创建一个长度为N+1的布尔数组，用来表示每个数是素数还是合数。将数组中的值初始化为true，表示所有数都是素数。然后，从2开始，逐个遍历数组中的数字。如果当前数字为素数，那么将它的倍数（除了自己本身）标记为合数，即将相应位置的布尔值设置为false。然后，在数组中找到下一个为true的数字作为下一个素数，继续进行相同的操作，直到选取的素数的平方大于给定范围。

例如，对于给定范围N=30，首先创建一个长度为31的布尔数组，表示每个数字是否为素数。然后，开始从2开始遍历数组。2是素数，将它的倍数4， 6， 8， ....标记为合数，将数组中相应位置的值设置为false。然后，找到下一个为true的数字3，继续将它的倍数6， 9， 12， ....标记为合数。依此类推，直到选取的素数的平方大于给定范围。最终，数组中为true的位置就是素数。

筛选法的时间复杂度为O(nloglogn)，其中n为给定范围内的数的个数。它的优点是在给定范围内的素数筛选速度快，适用于小范围的素数筛选问题。同时，筛选法可以进一步优化，使用空间换时间的方式，减少存储空间的使用。