Sundaram筛法C#实现的时间复杂度疑问

云原生阿岚

2026-4-21

你好，你的观察非常敏锐——确实，你当前的实现因为使用了Enumerable.Except，导致实际的时间复杂度和预期的O(n logn)有明显偏差，甚至可能达到你担心的O(n² logn)，问题主要出在两个关键点上：

Enumerable.Except的隐藏开销与误解
你担心的O(n² logn)复杂度并非杞人忧天：如果用朴素的嵌套循环实现“求差集”逻辑，那确实会是O(n * m)（m是Candidates序列的长度，约O(n logn)）。虽然.NET中Enumerable.Except默认用HashSet做了优化，理论平均复杂度是O(n + m)，但这里有两个拖慢性能的问题：
1. BigInteger的哈希计算和相等比较开销远大于普通值类型，会拉高实际运行耗时；
2. 你的Candidates()方法会生成大量重复的x值（不同的i、j组合可能得到同一个x），这些重复值虽然会被HashSet自动去重，但生成它们的过程已经浪费了不必要的计算资源，这部分额外开销会让实际复杂度接近O(n²)。
偏离了Sundaram筛法的核心——原地标记思想
传统Sundaram筛法能做到O(n logn)复杂度的核心，是用标记数组（而非生成两个序列再求差）来高效标记需要排除的数：
1. 初始化一个标记结构（比如BitArray），默认所有数都未被排除；
2. 遍历i和j计算x，只要x≤n就标记该位置；
3. 最后遍历标记结构，把未被标记的数转换为奇质数即可。

下面是优化后的实现，严格遵循O(n logn)复杂度：

public static IEnumerable<BigInteger> SieveOfSundaram(BigInteger n)
{
    if (n < 1)
        yield break;
    
    // 用BitArray节省内存，标记需要排除的数
    var isExcluded = new BitArray((int)n + 1);
    
    for (BigInteger i = 1; i <= n; i++)
    {
        for (BigInteger j = i; ; j++)
        {
            var x = i + j + 2 * i * j;
            if (x > n)
                break;
            isExcluded[(int)x] = true;
        }
    }
    
    // 单独返回唯一的偶质数2
    yield return 2;
    
    // 收集未被排除的数，转换为奇质数
    for (BigInteger i = 1; i <= n; i++)
    {
        if (!isExcluded[(int)i])
        {
            yield return 2 * i + 1;
        }
    }
}

这个版本的优势：

标记阶段没有重复计算，每个x只被标记一次，严格控制在O(n logn)的计算量；
用BitArray比生成完整序列节省大量内存，尤其适合处理较大的n；
整体复杂度为O(n logn) + O(n) = O(n logn)，完全符合Sundaram筛法的理论复杂度。

备注：内容来源于stack exchange，提问作者vvg