如何求素数java

判断素数的基本方法

素数是大于1的自然数，且只能被1和自身整除。在Java中，可以通过以下方法判断一个数是否为素数：

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

• 优化点：只需检查到 Math.sqrt(num)，因为如果存在大于平方根的因数，必然存在对应的小于平方根的因数。

打印范围内的素数

如果需要打印某个范围内的所有素数，可以结合循环调用上述方法：

public static void printPrimesInRange(int start, int end) {
    for (int i = start; i <= end; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

埃拉托斯特尼筛法（高效生成素数）

对于生成大量素数（如小于等于n的所有素数），筛法效率更高：

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

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

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

• 原理：标记非素数的倍数，剩余未标记的即为素数。
• 时间复杂度：O(n log log n)，远优于逐个判断。

实际应用建议

• 小范围判断：直接使用 isPrime 方法。
• 大范围生成：优先选择筛法，避免重复计算。