java 如何编写素数

判断素数的方法

素数是大于1的自然数，且只能被1和它本身整除。在Java中，可以通过多种方法判断或生成素数。

基础判断方法

使用循环检查从2到该数的平方根范围内是否有能整除的数。若没有，则该数为素数。

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

优化方法（埃拉托斯特尼筛法）

适用于生成一定范围内的所有素数。通过标记非素数的方式筛选素数。

public static void sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    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 + " ");
        }
    }
}

示例调用

public static void main(String[] args) {
    int number = 29;
    if (isPrime(number)) {
        System.out.println(number + " 是素数");
    } else {
        System.out.println(number + " 不是素数");
    }

    System.out.println("30以内的素数：");
    sieveOfEratosthenes(30);
}

输出结果

29 是素数
30以内的素数：
2 3 5 7 11 13 17 19 23 29

注意事项

• 基础方法适用于单个数的判断，时间复杂度为O(√n)。
• 筛法适用于批量生成素数，时间复杂度为O(n log log n)，但空间复杂度较高。
• 对于极大数的素数判断，可能需要更高效的算法（如Miller-Rabin测试）。