什么是素数？

素数（质数）是大于1的自然数，只能被1和自身整除。2是最小的素数。

基础检测：试除法

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

时间复杂度 O(n)，对大数太慢。

优化1：只需检查到 √n

若 n 有因子 a×b，则至少一个 ≤ √n。

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

优化2：跳过偶数

除了2，所有偶数都不是素数。

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

生成素数：埃拉托斯特尼筛法

要生成 ≤N 的所有素数，用布尔数组标记合数。

public static List<Integer> sieve(int N) {
    boolean[] composite = new boolean[N + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= N; i++) {
        if (!composite[i]) {
            primes.add(i);
            for (long j = (long)i * i; j <= N; j += i) {
                composite[(int)j] = true;
            }
        }
    }
    return primes;
}

时间复杂度 O(N log log N)，极高效。

小结

• 单数检测用 √n + 跳过偶数。

• 批量生成用 筛法。

• 注意整数溢出（用 long 处理 i*i）。