使用筛法生成素数的 C# 程序:

 1: using System;
 2: using System.Collections.Generic;
 3: 
 4: namespace Skyiv.Utils
 5: {
 6:   public static class Primes
 7:   {
 8:     public static int[] GetPrimes(int low, int high, bool hasSentinel = false)
 9:     {
10:       var primes = new List<int>();
11:       var composite = GetCompositeArray(high);
12:       for (var i = 2; i < composite.Length; i++)
13:         if (!composite[i] && i >= low) primes.Add(i);
14:       if (hasSentinel) primes.Add(high + 1);
15:       return primes.ToArray();
16:     }
17: 
18:     public static bool[] GetCompositeArray(int max)
19:     {
20:       int limit = (int)Math.Sqrt(max);
21:       var composite = new bool[max + 1];
22:       for (int i = 2; i <= limit; i++)
23:         if (!composite[i])
24:           for (int j = i * i; j <= max; j += i)
25:             composite[j] = true;
26:       return composite;
27:     }
28:   }
29: }

简要说明:

  • GetCompositeArray 方法返回一个布尔数组,当数组下标是合数时,其值为true
    • 首先将该布尔数组初始化为false,即假设数组中全是素数。(第 21 行)
    • 设上限为max,则从 2 开始,循环递增至 Sqrt(max)。(第 22 行)
    • 在循环中,如果当前元素i是素数(第 23 行),从i*i开始循环,以步长i递增,直到max(第 24 行),将其设为true(第 25 行)。这就是筛去i的所有倍数的步骤。
  • GetPrimes 方法返回lowhigh之间的所有素数。它调用 GetCompositeArray 方法来筛掉所有合数,然后将留下的素数放到primes数组中。如果hasSentinel为真,则尾部附加一个哨兵,该哨兵的值大于high,但不一定是素数。

参考资料

  1. Wikipedia: Sieve of Eratosthenes