改进后埃拉托斯特尼筛的运行速度变慢

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;
}

运行< code > sieve 22 max _ Basic(100)，查看一些倍数是否大于1(例如:< code>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

然后，我尝试通过使用存储每个数字的最小素数（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的倍数时，我不会划掉具有< code>spd[mul]的数< code>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亿

< code>Sieve22Max_Basic只需6s，而< code>Sieve22Max_Enh需要10s以上才能完成

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

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