java如何编程质数

判断质数的方法

质数是指大于1的自然数，除了1和它本身外没有其他约数。在Java中可以通过以下方法实现质数判断：

基础判断法 从2开始遍历到该数的平方根，检查是否有能整除的数：

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

优化方法（跳过偶数） 对于大于2的偶数直接排除：

public static boolean isPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

打印指定范围内的质数

埃拉托斯特尼筛法 高效找出小于等于n的所有质数：

public static void sieveOfEratosthenes(int n) {
    boolean[] prime = new boolean[n+1];
    Arrays.fill(prime, true);

    for (int p = 2; p*p <= n; p++) {
        if (prime[p]) {
            for (int i = p*p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (prime[i]) System.out.print(i + " ");
    }
}

性能优化建议

对于需要重复判断质数的场景，可以预先生质数表。大数判断时可采用Miller-Rabin概率测试等更高级算法。注意int类型的数值范围限制（最大2147483647），处理更大数值需使用long或BigInteger类型。