1. 什么是质数？
首先来看质数的概念：
质数（Prime number），又称素数，指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数。（也可定义为只有 1 与该数本身两个正因数的数）
图 1 数字 12 不是质数，而数字 11 是质数
如上图所示，数字 12 可以将每 4 个分成一组，一共 3 组；而数字 11 将每 4 个、每 5 个、每 3 个分成一组都无法全部分完，而有剩余，因此将数字 11 称为质数。
2. 如何判断是否为质数？
质数的特点如下：
一个自然数（如 1、2、3、4、5、6 等）若恰有两个正约数（1 及此数本身），则称之为质数。
方法 1
根据质数的约数只有 1 和本身这一特点，可以首先想到最直观的方法。第一种方法就是判断一个数是否能被比它小的数整除。
方法 1 的时间复杂度是 O(n)。
public static boolean isPrime(int n){
//n<=3时，质数有2和3
if (n <= 3) {
return n > 1;
}
//当n>3时，质数无法被比它小的数整除
for(int i = 2; i < n; i++){
if (n % i == 0) {
return false;
}
}
return true;
}
方法 2
当一个数不是质数时，必定存在两个约数，一个大于等于 sqrt(n)，另一个小于 sqrt(n)。利用这种特性，可以对方法 1 进行改进，只判断数 n 能否被小于 sqrt(n) 的数整除。
方法 2 的时间复杂度是 O(sqrt(n))。
图 2 筛选判断集，只选择小于等于 sqrt(n) 的集合
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
//判断一个数能否被小于sqrt(n)的数整除
int sqrt = (int)Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
方法 3
任一偶数一定能分解为 2 和其他偶数 / 奇数的积，因此一个数不能被 2 整除，那么这个数一定不能被其他偶数整除。利用这个特点，可以对方法 2 进行改进，判断数 n 能否被小于 sqrt(n) 的奇数整除。
方法 3 的时间复杂度是 O(sqrt(n)/2)。
图 3 进一步筛选判断集，只选择小于等于 sqrt(n) 的奇数
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
//只需判断一个数能否被小于sqrt(n)的奇数整除
int sqrt = (int)Math.sqrt(n);
for (int i = 3; i <= sqrt; i += 2) {
if(n % 2 == 0 || n % i == 0) {
return false;
}
}
return true;
}
方法 4
质数的分布具有特点，经过证明可以得到，（**大于等于 5 的）质数一定和 6 的倍数相邻，一定是 6x-1 或 6x-1。**利用这种特性。可以对整数进行筛选，只判断那些是 6x-1 或 6x-1 的整数是否为质数。
图 4 筛选数据集，只选择 6 的倍数相邻的数
证明过程如下：
令 x≥1，将大于等于 5 的自然数表示如下： ······6x-1，6x，6x+1，6x+2，6x+3，6x+4······（相邻 6 个数为一组）
在以上的数字中，6x、6x+2 和 6x+4 是偶数，一定不是质数；6x+3 可以分解为 3(2x+1)，不是质数，因此质数只能是 6x-1 和 6x+1。
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
// 只有6x-1和6x+1的数才有可能是质数
if (n % 6 != 1 && n % 6 != 5) {
return false;
}
// 判断这些数能否被小于sqrt(n)的奇数整除
int sqrt = (int) Math.sqrt(n);
for (int i = 5; i <= sqrt; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}