1

我正在阅读 MathBlog 上 Project Euler Problem 12 的解决方案，但我在理解代码背后的逻辑时遇到了一些麻烦。该程序使用素数分解来找到三角形数的除数。

private int PrimeFactorisationNoD(int number, int[] primelist) {
    int nod = 1;
    int exponent;
    int remain = number;

    for (int i = 0; i < primelist.Length; i++) {
        // In case there is a remainder this is a prime factor as well
        // The exponent of that factor is 1
        if (**primelist[i] * primelist[i] > number**) {
            return nod * 2;
        }

        exponent = 1;
        while (remain % primelist[i] == 0) {
            exponent++;
            remain = remain / primelist[i];
        }
        nod *= exponent;

        //If there is no remainder, return the count
        if (remain == 1) {
            return nod;
        }
    }
    return nod;
}

除了突出显示的部分“primelist[i] * primelist[i] > number”外，我了解程序的大部分内容。我很难理解这行代码的必要性。我将用一个例子来说明我的观点。假设我有一个数字 510 = 2*3*5*17。仅当 Primelist 到达第 23 位时，突出显示的代码才会为真。但是当列表到达第 17 位时，条件保持 == 1 将为真，并且程序将退出循环。如果我将代码更改为 if(remain==primelist[i]) 会更好吗，因为当primelist变为数字17而不是21时循环将结束？

4

2 回答 2

2

if 条件在某些情况下会加速代码（尽管它应该用“remain”代替“number”）。一旦达到 primelist[i]，我们就知道剩余不能被 primelist[0] 通过 primelist[i-1] 整除。如果 primelist[i]^2>remain 则我们可以得出结论，remain 是 primelist[i] 和 primelist[i]^2-1（包括）之间的某个素数，就好像保持 = ab 那么 a,b 都必须是至少 primelist[i] 所以剩下的至少是 primelist[i]^2，这是一个矛盾。因此我们可以停止寻找除余的素数。

举个更快的例子，取 number=7。然后当我们达到 3 时触发条件（如 3^2=9>7），因此我们不需要检查直到 7 的所有素数。

于 2013-05-18T05:15:14.457 回答
0

首先，它应该更好地使用remain：

primelist[i] * primelist[i] > remain

remain这是一种优化，因为和的平方根之间不能有除数remain，所以你只剩下因子remain了。

另外，变量名exponent是骗人的，它确实包含指数加一。最好将其初始化为零并乘以exponent + 1.

于 2013-05-18T07:32:14.813 回答