埃氏筛法

---

最近C程刚好讲到素数的求法，在实现了基础的方法后，我也学习了埃氏筛法，打算记录下来，以备不时之需。

---

埃氏筛法(sieve of Eratosthenes)

埃氏筛法又称为素数筛，是一种求解小范围素数的有效方法。
具体步骤如下：

1. 输入一个$[2, n]$区间，保存在列表中。
2. 把列表中可以被$2$整除的数筛除。
3. 把列表中可以被${3 + 2m(m = 0, 1, 2…[\frac{n-3}{2}])}$整除的数筛除。
4. 获取$[2, n]$区间内的所有素数。

总体来说，埃氏筛法是用空间换取了时间，时间复杂度为${O(Nlog(logN))}$。

代码实现

C#实现代码如下：

static List<int> Sieve(int n)
{
    List<int> list = new List<int>();

    if (n >= 2)
        list.Add(2);
    else
        return null;

    for (int i = 3; i <= n; i++)
    {
        if (i % 2 != 0)
            list.Add(i);
        else
            list.Add(-1);
    }

    for (int i = 3; i * i <= n; i += 2)
    {
        for (int j = 1; j < list.Count; j++)
        {
            if (list[j] != i && list[j] % i == 0)
                list[j] = -1;
        }
    }

    return list;
}

上述代码用$-1$标记删去的项，在调用该方法时，通过判断该值即可获取相应素数。

---