【面试必备 100题 系列 】- 001 - 判断 一个数 是不是 质数 / 素数
一、命题分析：
质数 又称 素数。指整数在一个大于1的 自然数 中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为 合数 。1和0既非素数也非合数。素数在 数论中有着很重要的作用。
二、答案解析：1、简洁、低效方案：
public static boolean isPrime(int n){ if (n <= 3) { return n > 1; } for(int i = 2; i < n; i++){ if (n % i == 0) { return false; } } return true;}
首先，过滤一下小于等于 3 的数，因为小于等于3的自然数只有 2 和 3 是质数/ 素数。
然后，我们只需要从 2 开始，一直到小于其自身，依次判断能否被 n 整除即可，能够整除则不是质数/ 素数，否则是质数/ 素数。
2、优化方案：
假设 n 是合数，必然存在 非1 的两个约数 p1 和 p2，其中 p1<=sqrt(n)，p2>=sqrt(n)。
由此我们可以改进上述方法优化循环次数。如下：
public static boolean isPrime(int n) { if (n <= 3) { return n > 1; } int sqrt = (int)Math.sqrt(n); for (int i = 2; i <= sqrt; i++) { if(n % i == 0) { return false; } } return true;}3、最优方案：
质数还有一个不为人知的特性：
基于这个理论我们不难推算出：
a、能被 6 整除的，肯定不是质数/ 素数，可以肯定的是，6x 不是质数/ 素数；
b、能被 2 / 3 整除的，肯定不是 质数/ 素数， 因此，6x+2 / 6x+3/ 6x+4 肯定也不是质数/ 素数；
那么，就剩下 6x+1 和 6x+5 (即等同于6x-1) 可能是质数/ 素数了。
得出方案：循环的步长可以设为 6，每次只判断 6 前后的两个数即可。
public static boolean isPrime(int num) { if (num <= 3) { return num > 1; } // 不在6的倍数两侧的一定不是质数 if (num % 6 != 1 && num % 6 != 5) { return false; } int sqrt = (int) Math.sqrt(num); for (int i = 5; i <= sqrt; i += 6) { if (num % i == 0 || num % (i + 2) == 0) { return false; } } return true;}