java如何算质数

判断质数的方法

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

基础判断法

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

优化方法1 - 减少循环次数 只需检查到√n即可，因为如果n能被大于√n的数整除，那么对应的因数一定小于√n。

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

优化方法2 - 跳过偶数 除了2，所有偶数都不是质数，可以跳过偶数检查。

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

打印质数列表

打印1到n之间的所有质数：

public static void printPrimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (isPrimeOptimized(i)) {
            System.out.print(i + " ");
        }
    }
}

性能更高的算法

对于需要大量质数判断的情况，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）：

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 + " ");
        }
    }
}

这些方法提供了从简单到高效的质数判断和生成方案，可根据具体需求选择合适的方法。对于大多数应用场景，优化后的单数判断方法已经足够高效。当需要处理大量质数时，筛法是更好的选择。