c# - Eratosthenes 筛法改进后运行速度变慢

Question

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

我已经实现了两个返回范围 [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 的倍数时，我不会划掉数字 mul有 spd[mul] < p因为mul被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 Sieve22Max_Enh 仅需 6 秒需要超过 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 循环条件下)，检查 mul * p < n .
• 增量+=并循环条件检查 <在两个循环中是相同的；检查spd[mul] >= p并更改 BitArray 中的值在他们花费的时间上具有可比性；但是额外的操作 mul * p在第二个循环中，条件是乘法——它很昂贵!
• 但是还有，对于第二个循环的每次迭代，如果spd[mul] >= p是true ，然后我们也执行:mul * p (再次!)，转换为 int , 更改 BitArray 中的值, mul * p (第三次!)，我假设再次转换为 int在 spd 的索引中, 并在数组中赋值 spd .

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