埃拉托色尼筛 运行 改进后变慢

Question

我尝试通过避免删除素数的重复倍数来改进基本的埃拉托色尼筛法算法，但结果比我的预期更糟

我已经实现了两种方法 return 在 [2..max)

范围内素数

基本筛法

public static List<int> Sieve22Max_Basic(int n) {
    var primes = new List<int>();
    var sieve = new BitArray(n, true); // default all number are prime
    //int crossTotal = 0;

    int sqrt_n = (int)Math.Sqrt(n) + 1;
    for (int p = 2; p < sqrt_n; ++p) {
        if (sieve[p]) {
            primes.Add(p);
            //var cross = new List<int>();
            int inc = p == 2 ? p : 2 * p;
            for (int mul = p * p; mul < n; mul += inc) {
                // cross out multiple of prime p
                // cross.Add(mul);
                //++crossTotal;
                sieve[mul] = false;
            }

            //if (cross.Count > 0)
            //    Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
        }
    }
    //Console.WriteLine($"crossTotal: {crossTotal:n0}");

    for (int p = sqrt_n; p < n; ++p)
        if (sieve[p])
            primes.Add(p);

    return primes;
}

运行 Sieve22Max_Basic(100)，看到一些倍数超过一个（例如：45, 75, 63）

Prime 2, cross out: 4 6 8 ... 96 98
Prime 3, cross out: 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99
Prime 5, cross out: 25 35 45 55 65 75 85 95
Prime 7, cross out: 49 63 77 91

增强筛选

然后，我尝试通过使用存储每个数字的 smallest prime divisor (spd) 的数组来改进。

45 = 3 x 5      // spd[45] = 3
75 = 3 x 5 x 5  // spd[75] = 3
63 = 3 x 3 x 7  // spd[63] = 3

当遍历素数 p 的倍数时，我不会划掉具有 spd[mul] < p 的数字 mul 因为 mul 在 [=27] 之前被 spd[mul] 划掉=]

public static List<int> Sieve22Max_Enh(int n) {
    var sieve = new BitArray(n, true);
    var spd = new int[n];
    for (int i = 0; i < n; ++i) spd[i] = i;
    
    var primes = new List<int>();
    //int crossTotal = 0;

    int sqrt_n = (int)Math.Sqrt(n) + 1;
    for (int p = 2; p < sqrt_n; ++p) {
        if (sieve[p]) {
            primes.Add(p);

            //var cross = new List<int>();
            int inc = p == 2 ? 1 : 2;
            for (long mul = p; mul * p < n; mul += inc) {
                if (spd[mul] >= p) {
                    sieve[(int)(mul * p)] = false;
                    spd[mul * p] = p;
                    //++crossTotal;
                    //cross.Add((int)(mul * p));
                }
            }
            //if (cross.Count > 0)
            //    Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
        }
    }
    //Console.WriteLine($"crossTotal: {crossTotal:n0}");

    for (int p = sqrt_n; p < n; ++p)
        if (sieve[p])
            primes.Add(p);

    return primes;
}

测试

我在我的笔记本电脑上测试（核心 i7 - 2.6 Ghz），n = 10 亿

Sieve22Max_Basic 只需要 6 秒，而 Sieve22Max_Enh 需要 10 多秒才能完成

var timer = new Stopwatch();
int n = 1_000_000_000;

timer.Restart();
Console.WriteLine("==== Sieve22Max_Basic ===");
var list = Sieve22Max_Basic(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");

Console.WriteLine();

timer.Restart();
Console.WriteLine("==== Sieve22Max_Enh ===");
list = Sieve22Max_Enh(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");

您可以在 https://onlinegdb.com/tWfMuDDK0

试试

为什么会变慢？

Answer 1

比较原始版本和改进版本的两个循环。

原文：

int inc = p == 2 ? p : 2 * p;
for (int mul = p * p; mul < n; mul += inc) {
  sieve[mul] = false;
}

改进：

int inc = p == 2 ? 1 : 2;
for (long mul = p; mul * p < n; mul += inc) {
  if (spd[mul] >= p) {
    sieve[(int)(mul * p)] = false;
    spd[mul * p] = p;
  }
}

一些观察：

• 两个循环 运行 相同的迭代次数。
• 对于每次迭代，原始循环执行三个非常快速的操作：1) 更改 BitArray、mul += inc 中的值并检查 mul < n.
• 对于改进循环的每一次迭代，我们执行更多操作：检查spd[mul] >= p、mul += inc、mul * p（在for-loop条件下），检查mul * p < n.
• 增量+=和<的循环条件检查在两个循环中是相同的；检查 spd[mul] >= p 和更改 BitArray 中的值在花费的时间上具有可比性；但是第二个循环条件中的附加操作 mul * p 是乘法——它很昂贵！
• 但是also，对于第二个循环的每一次迭代，如果spd[mul] >= p是true，那么我们also 执行：mul * p（再次！），强制转换为 int，更改 BitArray 中的值，mul * p（第三次！），我假设再次强制转换为 int 在 spd 的索引中，并在数组 spd.
中赋值

总而言之，您的第二个改进循环的每次迭代在计算上都“更重”。这就是你改进后的版本变慢的原因。