判断一个数是不是质数(素数)

​

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;}

质数（也称为素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。换句话说，质数只能被1和它自身整除。

• 例如，2, 3, 5, 7, 11, 13, 17, 19, 23, 29等都是质数。

​

代码演示 判断给定整数n是否为质数的函数：

public boolean isPrime(int n) {
    if (n <= 3) {
        return n > 1; // 如果n小于等于3且大于1，则返回true
    }
    
    for (int i = 2; i < n; i++) { // 从2开始遍历到n-1
        if (n % i == 0) { // 如果n能被i整除
            return false; // 则n不是质数，返回false
        }
    }
    
    return true; // 遍历结束后，说明n不能被2到n-1之间的任何数字整除，所以n是质数，返回true
}

函数逻辑分析

1. 基本情况检查:

• 如果​​n​​小于等于3，那么只有当​​n​​大于1时才可能是质数。这里直接返回​​n > 1​​的结果。

1. 循环检查:

• 从2开始遍历到​​n-1​​，检查是否存在能够整除​​n​​的数。

• 如果找到任何一个数​​i​​能够整除​​n​​（即​​n % i == 0​​），则​​n​​不是质数，函数返回​​false​​。
• 如果整个循环都没有找到这样的数，说明​​n​​不能被2到​​n-1​​之间的任何数整除，因此​​n​​是质数，函数返回​​true​​。

复杂度分析

• 时间复杂度: O(n)，最坏的情况下需要遍历从2到n-1的所有数。
• 空间复杂度: O(1)，只使用了有限个额外的变量。

​