C#质数判定的高效算法（埃拉托斯特尼筛法详解：从原理到代码实现）

埃拉托斯特尼筛法原理

该算法由古希腊数学家埃拉托斯特尼提出，核心思想是：逐个标记合数，剩下的就是质数。步骤如下：

1. 创建一个布尔数组 isPrime[0..n]，初始全部设为 true。
2. 0 和 1 不是质数，设为 false。
3. 从2开始遍历到√n：
• 如果当前数 i 是质数（即 isPrime[i] == true），则将其所有倍数（从 i*i 开始）标记为 false。
4. 遍历结束后，数组中值为 true 的索引即为质数。

C# 实现埃氏筛

下面是一个完整的 C# 代码示例，用于生成小于等于给定上限的所有质数：

using System;using System.Collections.Generic;class PrimeSieve{    public static List<int> SieveOfEratosthenes(int n)    {        // 创建布尔数组，初始全为 true        bool[] isPrime = new bool[n + 1];        for (int i = 0; i <= n; i++)        {            isPrime[i] = true;        }        // 0 和 1 不是质数        isPrime[0] = false;        isPrime[1] = false;        // 从 2 开始筛选        for (int i = 2; i * i <= n; i++)        {            if (isPrime[i])            {                // 标记 i 的所有倍数为合数                for (int j = i * i; j <= n; j += i)                {                    isPrime[j] = false;                }            }        }        // 收集所有质数        List<int> primes = new List<int>();        for (int i = 2; i <= n; i++)        {            if (isPrime[i])            {                primes.Add(i);            }        }        return primes;    }    static void Main()    {        int limit = 100;        var primes = SieveOfEratosthenes(limit);        Console.WriteLine($"小于等于 {limit} 的质数有：");        Console.WriteLine(string.Join(", ", primes));    }}

代码说明

• bool[] isPrime：用于记录每个数字是否为质数。
• i * i <= n：只需遍历到√n，因为更大的因子已经被前面的数覆盖。
• j = i * i：从 i² 开始标记，因为更小的倍数（如 2i, 3i...）已被更小的质数处理过。
• 最终返回一个包含所有质数的 List<int>。

性能与应用场景

埃氏筛非常适合批量生成质数的场景，比如：

• 密码学中的大质数预处理
• 数学竞赛题中的质数统计
• 算法题中频繁查询质数（可先预处理再查询）

注意：如果你只需要判断单个大数是否为质数，埃氏筛可能不是最优选择（因为要分配大数组），此时可考虑米勒-拉宾等概率算法。但对于 C#质数判定 中的批量需求，埃拉托斯特尼筛法 依然是最经典高效的方案之一。

总结

通过本文，你已经掌握了如何用 C# 实现 埃拉托斯特尼筛法 来高效筛选质数。这种方法不仅逻辑清晰，而且性能优越，是学习 C#高效算法 的绝佳入门案例。希望你能动手敲一遍代码，加深理解！

如果你喜欢这篇教程，欢迎分享给更多正在学习 素数筛选 的朋友！