C# 演算法設計與分析：素數尋找的篩選法基礎實作（一）

素數判定與尋找策略

素數定義：大於 1 的自然數，除 1 與自身外無其他因數。單一數值判定素數最直觀法：從 2 試除至 n-1，若能整除則非素數。時間複雜度 O(n)，對大數極不效率。

尋找 ≤ n 所有素數若逐一判定，總複雜度 O(n²)。採用刪除法（篩選法）可大幅降低複雜度：

1. 將 2~n 所有整數存入陣列。
2. 依序刪除能被某些整數整除的數（非素數）。
3. 陣列剩餘元素即為素數序列。

演算法一：基礎篩選法實作

class prime {
  public static int[] PrimeList;
  public static void FindPrime(int n) {
    int[] IntList = new int[n];
    for (int p = 2; p <= n; p++) IntList[p-1] = p;

    for (int p = 2; p < Math.Sqrt(n); p++) {
      int j = p + 1;
      while (j <= n) {
        if ((IntList[j-1] != 0) && (IntList[j-1] % p == 0))
          IntList[j-1] = 0;
        j++;
      }
    }

    int i = 0;
    for (int p = 2; p <= n; p++)
      if (IntList[p-1] != 0) i++;
    PrimeList = new int[i];
    i = 0;
    for (int p = 2; p <= n; p++)
      if (IntList[p-1] != 0) PrimeList[i++] = IntList[p-1];
  }
}

關鍵邏輯說明

• 陣列索引 p-1 對應數值 p，0 表示已刪除（非素數）。
• 外層迴圈 p < Math.Sqrt(n)：超過平方根的數，其倍數必已被較小因數標記。
• 內層 j = p+1 起始：從 p 之後的數開始檢查是否為 p 的倍數。
• 兩次掃描：第一次統計素數個數配置 PrimeList，第二次實際填入值。

以 n=10 為例演示

初始陣列：[2,3,4,5,6,7,8,9,10]

• p=2：標記 4,6,8,10 → [2,3,0,5,0,7,0,9,0]
• p=3：標記 6,9 → [2,3,0,5,0,7,0,0,0] (6 已為 0)
• p=4：IntList[3]=5 ≠0，但 4 已被標記為 0？實際碼中 p 迴圈不跳過非素數，p=4 時會檢查 5,6,7,8,9,10 是否為 4 的倍數（無效率）。

結果：[2,3,5,7] 為 ≤10 素數。此為厄拉托斯特尼篩的基礎雛形，下文將進一步優化。