1 埃拉托色尼筛选法：排除法

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。 要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛

欧拉筛它利用了前缀和的概念，可以在更短的时间内找出一定范围内的所有质数。
它保证范围内的每个合数都被删掉（在 bool 数组里面标记为非素数），而且任一合数只被：

“最小质因数 × 最大因数（非自己） = 这个合数”的途径删掉。由于每个数只被筛一次，时间复杂度为 O(n)。

2 排除法的实现

这个Golang程序实现了以下功能：

创建一个布尔切片来标记每个数字是否为素数。
将0和1标记为非素数。
使用埃拉托色尼筛选法来标记非素数。
输出所有素数以及素数的总数

package main

import (
    "fmt"
    "math"
)

// GeneratePrimes generates all prime numbers up to numRange
func GeneratePrimes(numRange int) {
    // Mark all numbers as prime
    listNumbers := make([]bool, numRange)
    for i := range listNumbers {
        listNumbers[i] = true
    }

    // Cross out 0, 1 as they are not primes
    if numRange > 0 {
        listNumbers[0] = false
    }
    if numRange > 1 {
        listNumbers[1] = false
    }

    squareRoot := int(math.Sqrt(float64(numRange)))

    for p := 2; p <= squareRoot; p++ {
        if listNumbers[p] {
            for i := p * p; i < numRange; i += p {
                // Cross out non primes by marking them false
                listNumbers[i] = false
            }
        }
    }

    fmt.Printf("Primes up to %d:\n", numRange)
    total := 0
    for p := 0; p < len(listNumbers); p++ {
        if listNumbers[p] {
            fmt.Printf("%d ", p)
            total++
        }
    }
    fmt.Printf("\nTotal: %d\n", total)
}

func main() {
    numRange := 100 // Example range
    GeneratePrimes(numRange)
}

3 欧拉筛的实现和分析

欧拉筛法（Euler’s Sieve）和埃拉托斯特尼筛法（Sieve of Eratosthenes）都是寻找范围内所有质数的经典算法。两者的共同目标是高效地生成质数，但它们在实现细节上有所不同，导致在效率上有一些差异。

1. 算法步骤：

• 读取输入的数 n，将 2 至 n 所有整数记录在表中
• 从 i=2 开始，如果 i 在表中，则将 i 加入至素数列表中
• 遍历当前素数列表，筛去 i 素数倍的数
• 当遍历到能整除 i 的素数 p 时，筛去 i·p，停止对素数列表的遍历
• 重复 2, 3, 4，直到所有不超过 n 的整数都被遍历过
• 素数列表中的元素即为所求的不超过 n 的所有素数

2. 欧拉筛法原理

首先证明每个合数都会被筛去：

• 若 n 为合数，设其素因子分解为 n = p1·p2···pq，其中 p1 为最小的素数
• 由于任意小于 p1 的素数都不能整除 p2···pq，所以 n 会在 i = p2···pq 时被筛去
• 再证明每个合数只会被筛去 1 次：
• 设合数 n 即被 p1 筛去，也被 p1’ 筛去。那么有 n = q·p1 = q’·p1’，其中 p1 和 p1’ 均是 n 的素因子
• 不妨设 p1 < p1’，故 p1 和 p1’ 互素，故有 p1 | q’
• i = q’ 时，遍历素数到 p1 时有 i % p1 == 0，此时跳出循环，不会再遍历到后面的 p1’
• 故 n 不会被 p1’ 筛去，只会被其最小的素因子 p1 筛去

Go语言中的欧拉筛法实现：

    package main

    import (
        "fmt"
    )

    // 欧拉筛法
    const MAXN = 1000001

    var isPrime [MAXN]bool
    var Prime []int

    func GetPrime(n int) {
        // 初始化所有数为 true，假设它们是素数
        for i := 0; i <= n; i++ {
            isPrime[i] = true
        }
        isPrime[1] = false // 1 不是素数

        for i := 2; i <= n; i++ {
            if isPrime[i] {
                Prime = append(Prime, i) // i 是质数，加入质数列表
            }

            for j := 0; j < len(Prime) && i*Prime[j] <= n; j++ {
                // 将 i * Prime[j] 标记为非素数
                isPrime[i*Prime[j]] = false

                if i%Prime[j] == 0 {
                    break // 如果 i 是 Prime[j] 的倍数，退出循环
                }
            }
        }
    }

    func main() {
        n := 100
        GetPrime(n)
        fmt.Println("Prime numbers up to", n, ":")
        for _, p := range Prime {
            fmt.Printf("%d ", p)
        }
        fmt.Println()
    }

• 欧拉筛法的优点：

时间复杂度：欧拉筛法的时间复杂度为 O(n)，而埃拉托斯特尼筛法的时间复杂度为 O(nloglogn)。

欧拉筛法具有理论上的更优性能，尤其在处理大规模的数据时表现更好。

空间复杂度：欧拉筛法只对每个数进行一次标记，且每个合数都由其最小质因数筛选出，因此占用的空间较少。而埃拉托斯特尼筛法可能会多次标记相同的合数。

无重复标记：埃拉托斯特尼筛法会对每个合数标记多次（比如2的倍数，3的倍数等），而欧拉筛法通过只用最小质因数对合数进行标记，避免了重复标记操作。

• 欧拉筛法与埃拉托斯特尼筛法对比：

速度：欧拉筛法通常在处理非常大的范围时会比埃拉托斯特尼筛法更快，特别是在现代硬件上，减少了重复标记的操作。
内存使用：由于欧拉筛法避免了重复标记，通常在内存上更加高效，特别是在较大的范围时。
如果需要处理非常大的范围，欧拉筛法是更优选择；但在较小范围内，埃拉托斯特尼筛法的实现相对简单且性能也较为接近。

4 运行结果和分析

证明：

    package main

    import (
        "fmt"
    )

定义常量 MAXN：指定数组 isPrime 的大小。MAXN 是要处理的数的最大范围，这里最大处理范围为 1000000。

    const MAXN = 1000001  

声明 isPrime 数组和 Prime 切片：
isPrime 是布尔数组，表示一个数字是否是质数。
isPrime[i] == true 表示 i 可能是质数，isPrime[i] == false 表示 i 已被筛选掉，不是质数。
Prime 是存储所有找到的质数的切片。

    var isPrime [MAXN]bool
    var Prime []int

定义函数 GetPrime(n int)：该函数接受一个参数 n，表示我们要找到 2 到 n 范围内的所有质数。

    func GetPrime(n int) {

初始化数组 isPrime：将从 0 到 n 的所有元素设置为 true，表示最开始假设所有数都是质数（稍后会筛除不是质数的数）。

        // 初始化所有数为 true，假设它们是素数
        for i := 0; i <= n; i++ {
            isPrime[i] = true
        }

特别处理 1：将 isPrime[1] 设置为 false，因为 1 不是质数。

        isPrime[1] = false // 1 不是素数

遍历所有数字 i 从 2 到 n：逐个检查每个数字 i 是否是质数。

        for i := 2; i <= n; i++ {

如果 i 是质数：
如果 isPrime[i] 是 true，表示 i 还没有被筛掉，因此它是质数。
将 i 加入到 Prime 切片中，存储找到的质数。

            if isPrime[i] {
                Prime = append(Prime, i) // i 是质数，加入质数列表
            }

            for j := 0; j < len(Prime) && i*Prime[j] <= n; j++ {

筛选所有 i * Prime[j]：
遍历 Prime 切片中的每个质数 Prime[j]，并计算 i * Prime[j]，这个数字一定不是质数，因为它是 i 的倍数。
条件 i * Prime[j] <= n 保证不超过 n。

                // 将 i * Prime[j] 标记为非素数
                isPrime[i*Prime[j]] = false

将 i * Prime[j] 标记为非质数：将 isPrime[i * Prime[j]] 设置为 false，表示它不是质数。

                if i%Prime[j] == 0 {

优化步骤：如果 i 是 Prime[j] 的倍数，则停止内层循环，因为 i 及其更大的倍数已经在之前的循环中被处理过。

                    break // 如果 i 是 Prime[j] 的倍数，退出循环
                }
            }
        }
    }

    func main() {

完成质数筛选：经过外层和内层循环，所有从 2 到 n 的质数都会被找出并存入 Prime 切片中。

        n := 100
        GetPrime(n)
        fmt.Println("Prime numbers up to", n, ":")
        for _, p := range Prime {
            fmt.Printf("%d ", p)
        }
        fmt.Println()
    }

• 运行结果和分析

  Prime numbers up to 100 :
  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

代码中，外层枚举 i=1→n 。对于一个 i，经过前面的筛选，如果它还没有被筛掉，就加到质数数组 Prime[]中。
下一步，是用 i来筛掉一波数。

内层从小到大枚举 Prime[j]。 i×Prime[j] 是尝试筛掉的某个合数，其中，我们期望 Prime[j]是这个合数的最小质因数 (这是线性复杂度的条件，下面叫做“筛条件”)。

j 的循环中的break保障了最小质因数：

        if(i % Prime[j] == 0)
            break;

j循环到 i mod Prime[j]==0 就恰好需要停止的理由是：

下面用 s(smaller)表示小于 j的数，L(larger) 表示大于 j 的数。

• 1 i的最小质因数肯定是 Prime[j]。

（如果 i的最小质因数是 Prime[s] ，那么 Prime[s]更早被枚举到（因为我们从小到大枚举质数），当时就break）

既然 i的最小质因数是 Prime[j]，那么 i×Prime[j]的最小质因数也是 Prime[j]。所以，j 本身是符合“筛条件”的。

• 2 i×Prime[s]的最小质因数确实是 Prime[s]。

（如果是它的最小质因数是更小的质数 Prime[t]，那么当然 Prime[t]更早被枚举到，当时就要break）

这说明 j 之前（用 i、×Prime[s]的方式去筛合数，使用的是最小质因数）都符合“筛条件”。

• 3 i×Prime[L]的最小质因数一定是 Prime[j]。

（因为 i的最小质因数是 Prime[j]，所以 i×Prime[L]也含有 Prime[j]这个因数（这是 i 的功劳），所以其最小质因数也是 Prime[j]（新的质因数 Prime[L] 太大了））

这说明，如果 j继续递增（将以 i×Prime[L]的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

当 i还不大的时候，可能会一层内就筛去大量合数，看上去耗时比较大，
但是由于保证了筛去的合数此后将不会再被筛（总共只筛一次），复杂度是线性的。
到 i接近 n时，每层几乎都不用做什么事。