我再次从 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);
数除数（）：
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
.
如何优化我的代码？这些公式是最好的解决方案吗？我觉得找到所有主要因素，然后实施公式将比我已经拥有的程序花费更长的时间。
非常感谢，
贾斯蒂安
编辑：
在任何人开始发布链接之前，我已经在 SO 中查看了类似的问题，但没有任何运气 - 我只是想不出他们的方法的实现会比我已有的方法运行得更快。
编辑2：
我在 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- 不比其他方法快太多，但尚未优化。但是，它有效。