java - 欧拉12号项目:具有500个除数的三角形数

我正在阅读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]>数字”。我很难理解这一行代码的必要性。我将通过一个例子来说明我的观点。假设我有一个数字510 = 2 * 3 * 5 * 17。仅当Primelist转到数字23时，突出显示的代码才为true。但是，当列表变为17时，条件== 1将为true，程序将退出循环。如果将代码更改为if（remain == primelist [i]），会更好些，因为当primelist变为17而不是21时循环将结束吗？

最佳答案

在某些情况下，if条件可以加快代码的速度（尽管应该用“ remain”代替“ number”）。一旦到达primelist [i]，我们就会知道primelist [0]到primelist [i-1]不能将其余部分整除。如果primelist [i] ^ 2> main仍然存在，那么我们可以得出结论，remain是primelist [i]和primelist [i] ^ 2-1（含）之间的一些质数，就像remain = ab一样，a，b都必须是至少primelist [i]，所以剩下的至少是primelist [i] ^ 2，这是一个矛盾。因此，我们可以停止搜索素数除法剩余。

对于更快的示例，请使用number = 7。然后当我们达到3时触发条件（因为3 ^ 2 = 9> 7），因此我们不需要检查所有素数到7。