优化素数生成算法

# 1. 素数生成算法概述

## 1.1 素数的定义与特性

素数是指在大于1的自然数中，除了1和本身外没有其他因数的数，例如2、3、5、7等。素数具有以下特性：
- 素数大于1。
- 只能被1和本身整除。
- 无法被其他自然数整除。

## 1.2 常见的素数生成算法简介

常见的素数生成算法包括：
- 简单的试除法：逐个判断每个数是否为素数。
- 厄拉托斯特尼筛法：通过每次标记某个数的倍数，逐步排除非素数。
- 欧几里得筛法：结合试除法和厄拉托斯特尼筛法的优点，减少不必要的遍历次数。

以上算法各有特点和适用场景，在实际应用中需要根据需求来选择合适的算法。

# 2. 基本素数生成算法分析

### 2.1 简单的试除法

简单的试除法是最基本的素数生成算法之一，其原理是对每个待检测的数字 n，从2开始逐个检测是否能整除，若不能整除则 n 是素数。这是一种直观易懂但效率较低的算法。

def trial_division(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# 示例
for num in range(1, 20):
    if trial_division(num):
        print(num, "是素数")

该算法时间复杂度较高，约为 O(sqrt(n))，在大数值范围下效率并不高。

### 2.2 厄拉托斯特尼筛法

厄拉托斯特尼筛法是一种较为高效的素数生成算法，其基本思想是从小到大逐个筛除合数，最终得到素数。算法流程如下：

1. 初始化一个从2到 n 的序列。
2. 从2开始，将每个素数的倍数全部标记为合数。
3. 找到下一个未被标记的数，即为下一个素数。
4. 重复步骤2和3，直到所有数均被标记。

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    List<Integer> primes = new ArrayList<>();
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }

    return primes;
}

// 示例
List<Integer> primes = sieveOfEratosthenes(20);
System.out.println("素数列表：" + primes);

厄拉托斯特尼筛法的时间复杂度为 O(n*log(log(n)))，相比试除法有了显著的提升。

### 2.3 欧几里得筛法

欧几里得筛法是一种改进的素数生成算法，通过消除重复标记优化了厄拉托斯特尼筛法的空间复杂度。具体步骤如下：

1. 初始化一个从2到 n 的序列。
2. 从2开始，将每个素数的倍数标记为合数，但标记时只标记未被之前素数整除的数。
3. 找到下一个未被标记的数，即为下一个素数。
4. 重复步骤2和3，直到所有数均被标记。

欧几里得筛法消除了冗余的标记，节省了空间开销，其时间复杂度与厄拉托斯特尼筛法相似。

func sieveOfEratosthenes(n int) []int {
    isPrime := make([]bool, n+1)
    primes := []int{}

    for i := 2; i*i <= n; i++ {
        if !isPrime[i] {
            for j := i * i; j <=