java - Project Euler 12，Java解决方案尝试，递归错误？

Question

我只需要一些关于改进问题解决方案的指导。请不要给我解决方案，因为我想自己完成。这是我使用递归解决 Project Euler Prob 12 的尝试。该问题要求第一个除数超过 500 的三角数。

我没觉得有什么问题； Eclipse 也没有显示任何错误。它只是继续运行而没有得到答案。

public class P012 {
    public static void main(String[] args) {

        int m=2;
        int c=1;
        int d=(c*(c+1)/2);

        while (numDivs(d,m)<=499) {
            c++;
            d=(c*(c+1)/2);
        }
        System.out.println(d);

    }

    public static int numDivs(int a, int b) {
        int foo=2;
        while (b < a/2) {
            if ((a%b)==0)
                foo++;
            b++;
            numDivs(a,b);
        }
        return foo;

    }
}

Answer 1

你使用的是一个非常幼稚的算法。您可能应该改进这一点。

1) 您确定答案适合 int 吗？
想一想，做一些测试。

2) 您可以例如使用质因数分解
number 来计算它的除数。如果质因数分解是:
M = p1 ^ k1 * p2 ^ k2 * ... pN ^ kN,
那么M的约数计数为:
(k1+1)*(k2+1)*...*(kN+1)。

3) 您可能需要筛选所有素数，直至达到给定的预选值
(例如最多 10,000,000)以便更快地实现 2)。

4)即使采用这种幼稚的方法，我也不认为你的方法
逻辑上是正确的，即首先在几个小数字上进行测试。

另请参阅:

http://en.wikipedia.org/wiki/Divisor_function

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes