素数筛

素数筛

    素数筛，顾名思义，是一种把自然数集合[2,n]中的所有素数筛选出来的算法，通常应用于需要素数打表的题目。

    常用的素数筛算法有两种，分别为埃氏筛 O(nloglogn) 与欧拉筛 O(n)。

埃氏筛

最朴素的素数筛算法，核心数学原理为素数的倍数为和数。

思路如下：

对于一串数字：2，3，4，5，6，7，8，9，10

找到第一个未被删除的数字2，从2开始，删除其后所有的2的倍数：2、3、4、5、6、7、8、9、10

得到剩余的数组：2、3、5、7、9

接着找到下一个未被删除的数字3，也删除其后所有的3的倍数：2、3、5、7、9

得到剩余数组：2、3、5、7

接着应该找下一个未被删除的数字5，但是5大于sqrt(10)，所以终止遍历，不再查找。

最终得到的素数数组为：2、3、5、7

查看代码

/*生成2-100之间的全部素数*/

#include <cstdio>

using namespace std;

bool issum[100]; 

int main() {
	for (int i = 2; i*i <= 100; i ++)
		if (!issum[i]) 
			for (int j = i*i; j <= 100; j += i)
				issum[j] = true;
	return 0;
}

代码详解：

创建桶排的bool数组，表示下标这个数是否为和数。

开始循环，如果数字是素数，那就删去后续这个数的倍数；如果是和数就跳过。（和数总能写成素数的乘积，所以全部的和数都会被删除，不必担心跳过和数会遗漏）

当前删除数从i²开始，是因为对于当前素数i>2，i²之前的和数总能写成n×i×p₀，其中p₀为小于i的素数，这就说明i²之前的和数已通过p₀删除，无需重复删除；而当i＝2时，2、3都是素数，i²＝4才为第一个要删除的和数。

共循环sqrt(100)=10次，这是因为任意和数的最大质因子总不大于该和数的开方值，例如100的最大质因子为5，不超过它的开方值10。

欧拉筛

埃氏筛尽管提高了素数打表的效率，但它依然可能导致一个和数被重复遍历。

例如，对于和数225，由于225大于3²，所以它会在i=3的循环里被删除一次。同时，又因为225大于5²，所以它也会在i=5的循环里被删除一次。

这就降低了素数筛算法的效率，欧拉筛则通过维护一个新的素数数组解决了这个问题。

欧拉筛算法简化的核心为仅在该和数的最小质因子循环中把该和数删除一次。

思路如下：

对于一组数字：2、3、4、5、6、7、8、9、10、11、12

首先找到第一个数2是素数，所以放入素数数组：{ 2 }

接着从原数组的2开始，与素数数组里的每一个元素依次相乘，并删除乘积对应的数，这里仅删除2×2=4：2、3、4、5、6、7、8、9、10、11、12

接着找到下一个数3，放入素数数组：{ 2、3 }

从原数组的3开始，依次删除与素数数组元素的乘积：2、3、4、5、6、7、8、9、10、11、12

接着找到下一个数字4，由于4不是素数，所以不放入素数数组，但是仍要与素数数组{ 2、3 }相乘，并删除乘积：2、3、4、5、6、7、8、9、10、11、12

这里12不应该被4删去，因为12的最小质因子是2，它应该在某次循环值与2的乘积为12时才能被删除。

我们假想原数组循环到了6，6不是素数，不放入素数数组，但要与素数数组{ 2、3、5 }相乘，并删除乘积，12在这时才应该被删去。

那如何确保一个数仅在它的最小质因子循环中被删去呢？

在上面的所有循环中，循环到2时，素数数组中仅有{ 2 }，原数组中的2能被素数数组中的2整除，它们的乘积4被删除；

循环到3时，素数数组为{ 2、3 }，3不能被2整除，可以被3整除，乘积6、9都被删除；

循环到4时，素数数组为{ 2、3 }，4能被2整除，不能被3整除，乘积8被删除，乘积12却没有被删除；

假想循环到6时，容易想到素数数组为{ 2、3、5 }，6不能被2、3、5整除，我们结合上述规律，猜测乘积12、18、30均会被删除；

我们可以直观地总结出当前值删除乘积的终止条件：当原数组中的值a能被素数数组中的某个值p整除，就终止遍历素数数组。

下面是数学证明：

对于找到的值a，如果满足p₀|a且a≠p₀，那么对于p₀之后的素数p>p₀,总有a×p=n×p×p₀，由于p₀小于p，并且p0是第一个找到的能整除a的质因数，所以p0就是a的最小质因数，则应该在p0的循环中删去a；

如果p₀|a且a=p₀，那么p₀一定为当前素数数组的尾元素，所以遍历也会在p₀处结束。

总结一下，相比与埃氏筛，欧拉筛多维护了一个素数数组，无论循环到的值是否为素数，都要与素数数组相乘并删去乘积，并在满足上述终止条件时停止删除进入下一个循环，如果当前循环到的值为素数就放入素数数组。

查看代码

/*生成2-100之间的全部素数*/

#include <cstdio>
#include <vector>

using namespace std;

bool issum[100]; 
vector<int> prime;

int main(int argc, char* argv[]) {
	域名ze(0);
	for (int i = 2; i <= 100; i ++) {
		if (!issum[i]) 域名ace_back(i);
		for (int j = 0; i*prime[j] <= 100 && j < 域名(); j ++) {	// 防止乘积越界
			issum[i*prime[j]] = true;
			if(!(i%prime[j])) break;
		}
	}
	return 0;
}