C# 求 100 以內質數：經典篩法與試除法實作

試除法（適合小範圍）

List primes = new List();
for (int i = 2; i <= 100; i++) {
    bool isPrime = true;
    for (int j = 2; j * j <= i; j++) {
        if (i % j == 0) { isPrime = false; break; }
    }
    if (isPrime) primes.Add(i);
}
// 輸出: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

埃拉托斯特尼篩法（效率更高）

bool[] isComposite = new bool[101];
for (int i = 2; i * i <= 100; i++) {
    if (!isComposite[i]) {
        for (int j = i * i; j <= 100; j += i) isComposite[j] = true;
    }
}
for (int i = 2; i <= 100; i++) if (!isComposite[i]) Console.Write(i + " ");

教學重點

• 試除法直觀易懂，適合初學者理解質數定義。
• 篩法時間複雜度 O(n log log n)，大範圍（如 10^6）時優勢明顯。
• Visual Studio 2005 環境下均可正常編譯執行。