java输出1~100之间的全部素数的5种方式总结

下面是关于“java输出1~100之间的全部素数的5种方式总结”的完整攻略：

问题描述

给定一个数字n，请输出1～n之间的全部素数。其中，素数指的是只能被1和自身整除的正整数，比如2、3、5、7等。

方案总结

方式一：暴力法

暴力法是最简单、也是最容易想到的解决方案。它的思路是通过循环从2到n-1，逐个判断每个数字是否为素数。这种方法的缺点是时间复杂度较高。

public static void primeNumbers(int n) {
    boolean isPrime;
    for (int i = 2; i <= n; i++) {
        isPrime = true;
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            System.out.print(i + " ");
        }
    }
}

示例输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

方式二：优化暴力法

暴力法可以通过进行优化来提高效率。我们可以只判断2到i/2之间的数字是否为i的因子。以及，若i不能被2整除，则i也不可能被大于i/2的数字整除。因此我们可以在j循环中将范围缩小到2～i/2。

public static void primeNumbers2(int n) {
    boolean isPrime;
    for (int i = 2; i <= n; i++) {
        isPrime = true;
        for (int j = 2; j <= i/2; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            System.out.print(i + " ");
        }
    }
}

示例输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

方式三：优化暴力法（2）

在方式二的基础上，我们还可以进一步进行优化。对于每个待判断数字i，我们只需要判断它是否有小于等于根号i的因子。因此可以将j循环缩小到2～根号i。

public static void primeNumbers3(int n) {
    boolean isPrime;
    for (int i = 2; i <= n; i++) {
        isPrime = true;
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            System.out.print(i + " ");
        }
    }
}

示例输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

方式四：埃氏筛法

埃氏筛法是一种较为高效的求解素数的方法。它的原理是从2开始，将每个素数的倍数都标记为非素数（即false）。一个数如果没有被任何一个比它小的素数整除，那么它本身就是素数。埃氏筛法的时间复杂度约为O(nloglogn)。

public static void primeNumbers4(int n) {
    boolean[] isPrime = new boolean[n+1];
    Arrays.fill(isPrime, true);
    for (int i = 2; i <= Math.sqrt(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 + " ");
        }
    }
}

示例输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

方式五：线性筛法

线性筛法是在埃氏筛法的基础之上，进行了一定优化的算法。它使用一个表记录出所有的质数。其原理是保证每一个数只会被最小的质因子筛去，从而保证每个合数只会被筛一次，时间复杂度为O(n)。

public static void primeNumbers5(int n) {
    int[] primes = new int[n+1];
    boolean[] isPrime = new boolean[n+1];
    int count = 0;
    Arrays.fill(isPrime, true);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes[count++] = i;
        }
        for (int j = 0; j < count && i*primes[j] <= n; j++) {
            isPrime[i*primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            System.out.print(i + " ");
        }
    }
}

示例输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

总结

以上就是Java输出1～100之间的全部素数的5种方式总结。通过对不同方法的比较，可以看出优化算法和筛法的效率更高，而线性筛法更为快速和高效。我们可以根据具体情况选择不同的算法，以提高程序的运行效率和效果。