当前位置：首页 > Java

java如何算素数

2026-03-23 01:37:06Java

判断素数的基本方法

素数是大于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;
}

优化算法效率

检查除数时只需遍历到√n即可，因为若n能被大于√n的数整除，其对应的商必然小于√n。

对于大数判断，可以进一步优化：

跳过偶数（除2外）
使用6k±1规律（所有大于3的素数都符合6k±1形式）

public static boolean isPrimeOptimized(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

打印素数列表

生成指定范围内的素数列表：

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

使用筛法求素数

埃拉托斯特尼筛法适合批量找出范围内的所有素数：

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