在面试时，要求输出 2 到 N 之间的所有素数是一个经典的问题，通常会考察应聘者对算法和时间空间复杂度的理解。下面是思路的详细解释，以及 Java 代码实现。

思路

1. 素数定义：素数是大于1的自然数，且仅能被1和自身整除。
2. 方法选择：
   • 最直接的解法是对于每个数字 i，判断它是否为素数。这个判断过程是通过检查 i 是否能被小于等于 i 的所有整数整除来完成。显然，时间复杂度较高。
   • 更高效的方法是 埃拉托斯特尼筛法（Sieve of Eratosthenes）。该方法的思想是：从2开始，将所有2的倍数标记为非素数，然后依次处理3、4、5等，直到处理到 √N 为止。这个方法能够有效减少判断素数的次数。

时间复杂度和空间复杂度分析

1. 埃拉托斯特尼筛法的时间复杂度：
   • 时间复杂度是 O(N log log N)，这个复杂度是通过逐步标记每个合数来实现的，比暴力方法要高效得多。
2. 空间复杂度：
   • 空间复杂度是 O(N)，因为我们需要一个大小为 N 的布尔数组来存储每个数是否是素数。

Java 实现（埃拉托斯特尼筛法）

import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers {

    // 埃拉托斯特尼筛法：输出2到N之间的素数
    public static List<Integer> sieveOfEratosthenes(int N) {
        // 布尔数组，true表示该数是素数，false表示该数不是素数
        boolean[] isPrime = new boolean[N + 1];
        
        // 初始时，所有数字都假设为素数
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
        
        // 从2开始，标记所有合数
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                // 如果i是素数，将i的所有倍数标记为非素数
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 收集所有素数
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        
        return primes;
    }

    public static void main(String[] args) {
        int N = 50; // 可以根据需要修改N的值
        List<Integer> primes = sieveOfEratosthenes(N);
        
        // 输出素数
        System.out.println("2到" + N + "之间的素数：");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

代码解释

1. 布尔数组 isPrime[]：用于记录每个数字是否为素数，初始化时假设所有数字都为素数，之后逐步筛选。
2. 筛法核心：
   • 从 i = 2 开始，如果 i 是素数，则将 i 的所有倍数标记为非素数。注意，i 的倍数可以从 i*i 开始，因为 i 的更小的倍数（例如 2*i）已经在之前的步骤中被处理过。
3. 收集素数：遍历 isPrime[] 数组，所有值为 true 的位置对应的数字是素数，将它们加入结果列表 primes。

输出结果

如果 N = 50，输出的素数会是：

Copy Code2到50之间的素数：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47