Java函数-判断一个数字是否是素数
素数是指只能被1和自身整除的正整数，如2、3、5、7、11等。判断一个数字是否是素数是数学中的经典问题之一，在计算机编程中也经常需要用到。本文将介绍如何用Java编写一个函数来判断一个数字是否是素数。
思路
判断一个数字是否是素数，需要用到数学中的一个重要性质：若一个数n不是素数，则它可以分解成两个非1数的乘积，即n=a*b，其中a和b是大于1的正整数。因此，为了判断一个数是否是素数，只需在2到n-1的范围内寻找它的因数，如果找到了一个因数，则它不是素数；如果在该范围内没有找到因数，则它是素数。
代码实现
下面是一个用Java编写的判断素数的函数：
public static boolean isPrime(int n) {
// 小于2的数都不是素数
if (n < 2) {
return false;
}
// 在2到n-1的范围内寻找因数
for (int i = 2; i < n; i++) {
if (n % i == 0) {
// 找到因数，该数不是素数
return false;
}
}
// 范围内没有找到因数，该数是素数
return true;
}
该函数的参数是一个整数，如果该整数是素数，则返回true；否则返回false。该函数的实现很简单，先判断该数是否小于2，因为小于2的数都不是素数，然后在2到n-1的范围内寻找因数，如果找到了因数，则该数不是素数；如果没有找到因数，则该数是素数。
测试函数
为了验证上述的判断素数函数是否正确，我们可以编写一个测试函数，用一些已知的素数和非素数来测试该函数：
public static void testIsPrime() {
int[] nums = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75,
76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100};
for (int n : nums) {
boolean prime = isPrime(n);
if (prime && !isKnownPrime(n)) {
System.err.println(n + " is not prime but the function thinks it is");
} else if (!prime && isKnownPrime(n)) {
System.err.println(n + " is prime but the function thinks it's not");
}
}
}
该函数定义了一个整型数组nums，其中包含了一些已知的素数和非素数。对于nums中的每个数字n，调用isPrime函数来判断它是否是素数，并与其对应的是否为已知的素数或非素数进行比较，如果不一致则输出错误信息。
下面是一个完整的测试函数：
public static void main(String[] args) {
testIsPrime();
}
函数输出为空，说明所有的素数和非素数都被正确地判断了。
优化
上述的判断素数函数虽然简单，但是它的效率并不高。当我们需要判断一个大整数是否是素数时，该函数必须遍历该整数范围内的所有数来寻找因数，这会造成很大的计算开销。为了提高效率，我们可以采用一些优化的方法。
优化1：缩小搜索范围
根据上述的素数判断方法，只需要在2到n-1的范围内寻找因数，就可以判断一个数字是否是素数。但是，我们可以发现，只需要在2到√n的范围内寻找因数，就可以得到正确的答案。
这是因为，如果一个数字n不是素数，则它可以分解成两个非1数的乘积，即n=a*b，其中a和b是大于1的正整数。如果a>√n且b>√n，则a*b>n，与n=a*b矛盾；因此，必定有a≤√n或b≤√n，即至少有一个因子小于等于√n。因此，只需要在2到√n的范围内寻找因数，就可以得到正确的答案。
下面是优化后的判断素数函数：
public static boolean isPrime(int n) {
// 小于2的数都不是素数
if (n < 2) {
return false;
}
// 在2到√n的范围内寻找因数
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
// 找到因数，该数不是素数
return false;
}
}
// 范围内没有找到因数，该数是素数
return true;
}
优化2：跳过偶数
我们可以发现，除了2之外，所有的偶数都不是素数，因此，在查找质数时可以先判断是否是2，如果是2则返回true，否则可以用类似于“跳过偶数”的方法，在奇数中查找质数。例如，从3开始，间隔为2查找质数：
public static boolean isPrime(int n) {
// 小于2的数都不是素数
if (n < 2) {
return false;
}
// 如果是2，则返回true
if (n == 2) {
return true;
}
// 如果是偶数，则不是素数
if (n % 2 == 0) {
return false;
}
// 从3开始，间隔为2查找质数
for (int i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i == 0) {
// 找到因数，该数不是素数
return false;
}
}
// 范围内没有找到因数，该数是素数
return true;
}
测试函数也需要做相应的修改：
public static void testIsPrime() {
int[] nums = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,