素数的筛法

定义

素数， 又称质数， 指因数只有两个的数 （及自己和1）。
注意：1与0不是质数， 因为其因数个数小于2

求素数

法一：直接求解

基本的解法就是从定义入手， 既然定义是除了1与自己以外没有其它因数， 那么我们询问n是否是质数时就可以枚举x\((1< x < n)\)， 判断x是否是n的因数。
代码：

if (n <= 1) {//小于等于1就不是质数
	return 0;
}

for (int i = 2; i < n; i ++) {//枚举（1， n）之间的正整数， 判断是否有
	if(n % i == 0) {
		return 0;
	}
}

return 1;

优化

我们知道， 若\(n = x * y (x \le y, \{n, x, y\}\subseteq\mathbb R)\)则若\(x\notin\mathbb Z\)那么， \(y\)一定有\(y\notin\mathbb Z\), 若\(x\in\mathbb Z\)那么， \(y\)一定有\(y\in\mathbb Z\)， 所以我们其实只要枚举所有小于等于\(\sqrt[2]n\)的大于一整正数就行了。
代码：

if (n <= 1) {//小于等于1就不是质数
	return 0;
}

for (int i = 2; i <= sqrt (n); i ++) {//枚举（1， sqrt (n)）之间的正整数， 判断是否有
	if(n % i == 0) {
		return 0;
	}
}

return 1;

法二：埃拉托斯特尼筛法

我们知道， 每一个数都可以分解成若干个质数之积（证明方法：。。。没找到）， 所以我们只需要找到一个质数后将其倍数都置为无法选择， 就可以了。
代码：

vis[1] = 1;

for (int i = 2; i <= n; i ++) {
	if (vis[i] == 0){//如果没被置为是不是质数， 那就是是质数了
		for (int j = 2; j * i <= n; j ++) {
			vis[i * j];//将所有倍数都置为不是质数
		}
	}
}

return !vis[n];

这种方法还有另一个优势就是可以一次性处理\([1, n]\)的数是否为质数。

优化

若\(x\)为素数， 且有\(y\)是小于\(x\)正整数， 那么\(x * y\)就在\(x\)之前被\(y\)的某个质因数已经置为不是了。所以我们其实只需要从\(y * y\)开始往后更新\(y\)的倍数就就行了
代码：

vis[1] = 1;

for (int i = 2; i <= n; i ++) {
	if (vis[i] == 0){//如果没被置为是不是质数， 那就是是质数了
		for (int j = i; j * i <= n; j ++) {
			vis[i * j] = 1;//将所有倍数都置为不是质数
		}
	}
}

return !vis[n];

法三：线性筛

这种筛法是在埃拉托斯特尼筛法的基础上改进而来的。 埃拉托斯特尼筛法就算经过优化也可能会把一个数重复筛多次。 根据某个公理， 我们知道， 任意一个集合都有一个最小值与一个最大值， 所以每个数的质因数都有一个最小值， 如果我们每次筛数都只用这个数的最小质因数， 就可以将时间复杂度降到线性。每当我们循环到任意一个数\(n\)\((n\in\mathbb N, n可以不是质数)\)， 就将其质数倍给筛掉， 直到出现质数\(a_i\)\((a为质数集合)\)是n的因数时， 就跳出筛素数的循环， 因为\(a_i * n\)一定能被\(a_j * \frac {n} {a_i}(j > i)\)筛掉。
代码：

int ans = 0;//记录素数已有个数

vis[1] = 1;

for (int i = 2; i <= n; i++) {
	if (vis[i] == 0){
    	pn[++ans] = i;
	}
    	
    for (int j = 1; j <= ans && i * pn[j] <= n; j++) {
        vis[i * pn[j]] = 1;//将i的素数倍置为合数
            
        if (i % pn[j] == 0){//如果pn[j]是i的因数, 那么就用后面的数再去改变
            break;
        }
    }
}

return !vis[n];

方法分析

第一种方法

速度慢， 不过占用空间极小， 且在不超过范围的情况下只用两个变量， 适用于卡空间的题

第二种方法

速度中等， 空间中等， 而且与第三种的空间差不多， 一般来说只要会第三种基本不用这一种方法， 比较鸡肋。

第三种方法

空间占用较多， 不过时间非常快， 与第二种方法都可以一次性处理[1, n]之间的所有情况， 比较常用。

综上所述

题目中决定使用方法的就是数据范围， 在每个阶段的所开数组范围中都有不同的方法，只是第二种方法一般来说只用于知识点不够的情况下。