需要帮助优化Project Euler问题#12的解决方案

Question

我一直对Project Euler的挑战感到很开心,我注意到我的12号解决方案是我~593.275 ms每年最慢的解决方案之一.这是我在~1254.593 ms每个月的第10号解决方案的第二位.我所有的其他答案都花费不到3 ms最好1 ms.

问题12的我的Java解决方案:

主要():

int index = 1;
long currTriangleNum = 1;

while (numDivisors(currTriangleNum) <= 500) {
    index++;
    currTriangleNum += index;
}

System.out.println(currTriangleNum);

numDivisors():

public static int numDivisors(long num) {  
    int numTotal = 0;

    if (num > 1)
        if (num % 2 == 0) {
            for (long i = 1; i * i <= num; i++)
                if (num % i == 0)
                    numTotal+=2;
        } else {
            // halves the time for odd numbers
            for (long i = 1; i * i <= num; i+=2)
                if (num % i == 0)
                    numTotal+=2;
    }
    else if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else (num < 0)
        return numDivisors(num *= -1);

    return numTotal;
 }

.

看一下解决方案论坛,有些人发现这些公式(n =(p ^ a)(q ^ b)(r ^ c)...&d(n)=(a + 1)(b + 1)( c + 1)...)为他们工作,但我个人不知道它会如何更快; 也许是手动更快,但不是在程序中.

.

基本思考过程如下:

我们想要计算48中除数的数量.通过查看下面的因子树,我们可以得出结论:48 = (2^4)(3^1)[n =(p ^ a)(q ^ b)(r ^ c)...].

  48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3 

知道这一点,我们构造公式d(48) = (4+1)(1+1)[d(n)=(a + 1)(b + 1)(c + 1)...]以确定48有10个因子.

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

如何优化我的代码？这些配方是最好的解决方案吗？我觉得找到所有主要因素,然后实施公式需要的时间比我已有的程序要长.

非常感谢,

瑞斯蒂昂

编辑:

在任何人开始发布链接之前,我已经在没有任何运气的情况下查看了类似的问题 - 我只是想不起他们的方法的实现比我现有的更快.

EDIT2:

我在Eratosthenes筛选中的第二次尝试(针对问题10):

int p = 3, n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

运行~985.399 ms- 比其他方法快得多,但尚未优化.然而,它有效.

Answer 1

使用基础数学结构,这将显着改变程序的运行时间.顺便说一下,这也适用于问题10; 如果你不能在几毫秒内完成,你就使用了一种效率极低的算法.事实上,我建议你先解决问题10,因为问题12建立在它上面.

我将为下面的问题12提供一个更好的算法,但首先,这是一个观察,应该显着加快你的程序.如果两个数字x和y是互质的(即它们除1之外没有公约数),则d(x·y)= d(x)·d(y).特别地,对于三角形数,d(n·(n + 1))= d(n)·d(n + 1).因此,不是迭代三角形数n·(n + 1),而是遍历n:这将显着减小传递给d(n)的参数的大小.

如果你进行了这种优化,你会注意到你连续两次计算d(n)(一次为d((n-1)+1),一次为d(n)).这表明缓存d的结果是个好主意.下面的算法可以实现它,但也可以自下而上计算自上而下,这样更有效,因为乘法比分解要快得多.

问题10可以通过简单应用Eratosthenes筛来解决.填充大小为2000000的布尔数组(即位矢量),使得sieve[i]==trueif i为素数; 然后总结一下这些数字sieve[i]==true.

问题12可以通过Eratosthenes筛的概括来解决.不是sieve[i]使用表示是否i为素数的布尔值,而是使其成为一个数字,表示非素数的方式数,即除数的除数i.很容易修改Eratosthenes的基本筛子来做到这一点:而不是设置sieve[x*y]为false,添加1.

随后的几个项目Euler问题也受益于类似的方法.

您可能遇到的一个问题是,在问题12中,不清楚何时停止计算筛子.您可以通过两种方式了解它:
1.按需按块计算筛子,本身就是一项有价值的编程练习(这将需要更复杂的代码,第二种方法)
2.或者从高估边界开始:找到一些三角形数字有超过500的除数,你知道你会在之前或那个数字处停下来.

如果你意识到你只需要关心奇数就可以获得更多的时间,因为如果n是奇数,则d(2 ^ k·n)=(k + 1)·d(n),并且只给出k和n (2 ^ k·n)在二进制计算机上很快.我将把优化的细节留作练习.