C#算法設計與分析：尋找素數優化實踐（二）——埃拉托斯特尼篩法改進版

基礎篩法缺陷分析

經典篩法（從2到√n刪除倍數）存在三大效率問題：

1. 重複標記：如6被2和3各刪除一次，雖邏輯無衝突但浪費操作。
2. 統計步驟冗餘：先計算數組大小再賦值，可合併為單次遍歷。
3. 無效除數參與：已被標記為合數的數（如4）無需再作除數，因其倍數已被質因數覆蓋。

優化算法實現

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

        for (int p = 2; p <= Math.Sqrt(n); p++) {
            if (intList[p-1] == 0) continue; // 跳過合數
            int j = p * p; // 從p²開始，更小倍數已被處理
            while (j <= n) {
                if (intList[j-1] != 0) {
                    intList[j-1] = 0;
                    len--;
                }
                j += p;
            }
        }

        PrimeList = new int[len];
        int idx = 0;
        for (int p = 2; p <= n; p++) {
            if (intList[p-1] != 0) PrimeList[idx++] = intList[p-1];
        }
    }
}

關鍵改進：

• 外層循環遇合數直接continue，避免無效除數操作。
• 內層從p*p起步，減少重複標記。
• 統計素數個數與提取合併在單次遍歷中完成。

性能對比驗證

static void Main() {
    Console.WriteLine("Start!");
    var t1 = DateTime.Now; PrimeOptimized.FindPrime(100000); var t2 = DateTime.Now;
    var t3 = DateTime.Now; PrimeNaive.FindPrime(100000); var t4 = DateTime.Now;
    Console.WriteLine($"優化版: {(t2-t1).Ticks} ticks");
    Console.WriteLine($"原版: {(t4-t3).Ticks} ticks");
}

實測優化版耗時僅為原版的1/30 ~ 1/60。時間複雜度從近似O(n^1.5)降至O(n)量級，充分體現算法設計對性能的決定性影響。