java如何表达素数

判断素数的方法

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

基础判断法

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

优化方法 减少循环次数，只需检查到√n即可：

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

打印素数列表

打印指定范围内的所有素数：

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

使用埃拉托斯特尼筛法

高效生成素数列表的算法：

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

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

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

性能比较

• 基础方法时间复杂度：O(n)
• 优化方法时间复杂度：O(√n)
• 筛法时间复杂度：O(n log log n)

对于大规模素数计算，推荐使用筛法算法。小范围判断时优化方法即可满足需求。