我的Java解决方案Problem 12：

主要()：

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

.

围绕解决方案论坛,有些人发现these formulas(n =(p ^ a)(q ^ b)(r ^ c)…& d(n)=(a 1)(b 1) )…)为他们工作,但我个人不明白它会如何更快;手也可以更快,但不是在程序中.

.

基本思想过程如下：

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

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

知道这一点,我们构造公式d(48)=(4 1)(11)[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

.

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

非常感谢,

瑞斯蒂昂

编辑：

在任何人开始发布链接之前,我已经在SO中查看了类似的问题,没有任何运气 – 我只是想不到他们的方法的实现会比我已经有了更快的运行.

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 – 不会比其他方法快得多,但尚未优化.然而,它是有效的.