本文题目难度标识：🟩简单，🟨中等，🟥困难。

判断一个数是否为质数

给定一个正整数 n ，判断它是不是素数。

站内文章质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

暴力枚举

因此对于每个数 x，我们可以从小到大枚举 $[2,x−1]$ 中的每个数 y，判断 y 是否为 x 的因数。

// 未优化解法
public boolean isPrime(int x) {
	for (int i = 2; i < x; ++i) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

复杂度分析：

时间复杂度： $O(n)$
空间复杂度： $O(1)$

平方根优化

性质：对于合数 a，一定存在素数

p\le \sqrt{a}

使得

p\mid a

。

考虑到如果 y 是 x 的因数，那么 $x/y$ 也必然是 x 的因数，因此我们只要校验 y 或者 $x/y$ 即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 $[2, \sqrt{x}]$ 的区间中，因此我们只需要枚举 $[2, \sqrt{x}]$ 中的所有数即可。

// 优化解法
public boolean isPrime(int x) {
	for (int i = 2; i*i <= x; ++i) { 
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

复杂度分析：

时间复杂度： $O(\sqrt{n})$
空间复杂度： $O(1)$

6 倍原理优化

性质（6 倍原理）：所有大于 3 的素数都可以表示为

6n\pm 1

的形式。

但是与 6 的倍数相邻的不一定是素数，有可能是 6 倍邻数的倍数，例如 25、35、49，这些数就分别是 5，7 的倍数。

大于等于 5 的素数必定为 6 倍邻数证明：
6 倍以外的数分别有： $6n+1$ ， $6n+2$ ， $6n+3$ ， $6n+4$ ， $6n+5$
其中 $6n+2$ ， $6n+3$ ， $6n+4$ 三个数都可以分解：

\begin{aligned} 6n+2=2(3n+1)\\ 6n+3=3(2n+1)\\ 6n+4=2(3n+2)\\ \end{aligned}

所以以上三个数必不可能是素数，剩下的只有 $6n+1$ ， $6n+5$ 可能存在素数。

在判断 $6n+1$ 和 $6n+5$ 是否为素数过程中只需判断这个数是否为 6 倍邻数的倍数即可断定。

首先， $6n+2$ ， $6n+4$ 为偶数，不可能是 $6n+1$ ， $6n+5$ 这个两个奇数的因数，自然就不用判断；
然后， $6n+3=3(2n+1)$ ，所以 $6n+3$ 必为 3 的倍数，但是 $6n+1$ ， $6n+5$ 并不会是 3 的倍数。原因：

\begin{aligned} \frac{6n+1}{3}&=2n+\frac{1}{3}\\ \frac{6n+5}{3}&=2n+1+\frac{2}{3}\\ \end{aligned}

故 $6n+1$ 和 $6n+5$ ，要么是素数，要么为 $6m+1$ 和 $6m+5$ 的倍数。

利用这个性质我们还可以进一步优化代码：

对 1~3 进行特判；
先判断是否为 6 倍邻数，如果是则执行第二步；
判断这个数是否为 6 倍邻数的倍数，如若不是则这个数为素数。

public static boolean isPrime(int num) {
	if(num == 1) return false;
	
	if (num == 2 || num == 3) {
		return true;
	}

	//如果不与6的倍数相邻，肯定不是素数
	if (num % 6 != 1 && num % 6 != 5) {
		return false;
	}

	//对6倍邻数进行判断,是否为6倍邻数的倍数
	for (int i = 5; i <= Math.sqrt(num); i += 6) {
		if (num % i == 0 || num % (i + 2) == 0) {
			return false;
		}
	}
	return true;
}

多次判断质数

🟨 204. 计数质数 - 力扣（LeetCode）

给定整数 n ，返回所有小于非负整数 n 的质数的数量。

这道题的特点在于我们需要求出一组数是否是质数。如果对于每个数都执行 isPrime 方法，那么时间复杂度会达到 $O(n\sqrt{n})$ 。

下面介绍两种筛法。

埃氏筛

大埃拉托斯特尼筛法用来寻找不超过一个给定整数的所有素数。

考虑以下事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数。

例如寻找不超过 100 的素数：
- 不超过 100 的合数必定有一个不超过 10 的素因子。
- 小于 10 的素数有 2，3，5，7。
- 除了 2,3,5,7 以外，删除所有能被 2，3，5 或 7 整除的整数。
- 除了 1 以外，所有保留下来的都是素数。

我们设置 flags 数组，flags[i]==1 说明数 i 被标记，是合数，反之为质数。

// 未优化版本
public int countPrimes(int n) {
	int ans = 0; // 统计质数的数目
	int[] flags = new int[n]; 
	for(int i=2;i<n;i++){
		if(flags[i]==1)continue;
		ans++;
		for(int j=1;j*i<n;j++){
			flags[j*i]=1;
		}
	}
	return ans;
}

接下来我们还可以进行优化。对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2x 这个数，在外层循环 i==2 时已经被标记。

// 优化版本
public int countPrimes(int n) {
	int ans = 0; // 统计质数的数目
	int[] flags = new int[n]; 
	for(int i=2;i<n;i++){
		if(flags[i]==1)continue;
		ans++;
		for(int j=i;(long)j*i<n;j++){ // 避免 j*i 在循环初可能会出现整数溢出
			flags[j*i]=1;
		}
	}
	return ans;
}

复杂度分析：

时间复杂度： $O(n \log \log n)$ $O (n lo g lo g n)$ ：本质上就是求解 $\sum_p{n/p}$ $\sum_{p} n / p$ 的和，其中 p 为质数。
- 一个比较松的上界为 $O(n)\log n$ ，相当于考虑 $\sum_{i=1}^{n}{n/i}$ 的和，而 $O(\sum_{i=1}^{n}{n/i}) = O(n\sum_{i=1}^{n}{1/i})$ ，且 1 到 n 所有数的倒数和趋近于 $\log n$ 。
空间复杂度： $O(n)$

线性筛

在埃氏筛中还是存在冗余的标记操作，比如对于 45 这个数，它会同时被 3,5 两个数标记为合数。我们的目标是每个合数只被标记一次，而且是只被自己的最小因数标记。

相较于埃氏筛，我们多维护一个 primes 数组表示当前得到的质数集合。我们从小到大遍历，如果当前的数 x 是质数，就将其加入 primes 数组。

「标记过程」不再仅当 x 为质数时才进行，而是对每个整数 x 都进行。对于整数 x，我们不再标记其所有的倍数 x⋅x，x⋅(x+1)，…，而是只标记质数集合中的数与 x 相乘的数，即 x⋅primes_0，x⋅primes_1，…，且在发现 x mod primes_i==0 时终止标记。

为什么发现 x mod primes_i==0 时终止后续数的标记？因为 x mod primes_i==0，说明 x 本身携带着一个比 primes_i 更小（或相等）的因数 e，e=x/primes_i。如果我们不在此刻终止，而继续将 x⋅primes_{i+1} 标记为合数，但是这个合数的最小因子是 e，在前面已经被 e 标记过了，我们不应当重复标记，不然就会违反之前「合数只被自己最小因数标记」的规定。

public int countPrimes(int n) {
	int ans = 0;
	int[] flags = new int[n];
	List<Integer> primes = new ArrayList<>();
	for(int i=2;i<n;i++){
		if(flags[i]==0){
			primes.add(i);
		}
		for(int j=0;j<primes.size() && (long)primes.get(j)*i<n ;j++){
			int p = primes.get(j);
			flags[p*i]=1;
			if(i%p==0){
				break;
			}
		}
	}
	return primes.size();
}