java优化递归方法

Question

我有一些代码需要运行一些相当大的数字，它涉及到一个递归方法的递增，因此非常慢，以至于我甚至无法得到我想要的答案。有人能帮我优化一下吗？不过我是个初学者，所以我不能做任何非常复杂/困难的事情

public class Euler012{
    public static void main(String[]args){
        int divisors=0;
        for(long x=1;divisors<=501;x++){
            divisors=1;
            long i=triangle(x);
            for(int n=1;n<=i/2;n++){
                if(i%n==0){
                    divisors++;
                }
            }
            //System.out.println(divisors+"\n"+ i);
            System.out.println(i+": " + divisors);
        }
    }
    public static long triangle(long x){
        long n=0;
        while(x>=0){
            n+=x;
            x--;
            triangle(x);
        }
        return n;
    }
 } 

Answer 1

你不必每次都从头开始生成一个新的三角形数，如果你将值保存到一个变量中，然后在下一次迭代中向它添加x，你根本不需要使用三角形方法

Answer 2

第一：我不认为这是一个优化问题，因为这是一个小任务，但正如评论中提到的，你会做很多不必要的事情

好的，现在让我们看看你可以在哪里优化东西：

递归

递归的性能通常很差，尤其是在不保存值的情况下，这在您的示例中是可能的

例如：带保存值的递归三角形数函数

private static ArrayList<Integer> trianglenumbers = new ArrayList<>();

public static int triangleNumber(int n){
    if(trianglenumbers.size() <= n){
        if(n == 1)
            trianglenumbers.add(1);
        else
            trianglenumbers.add(triangleNumber(n-1) + n);
    }
    return trianglenumbers.get(n-1);
}

但正如@RichardKennethNiescior所提到的，你可以简单地使用以下公式： (n² + n)/2

但在这里我们也可以进行优化！ 你不应该做/2，而应该做*0.5甚至>>1（右移） 但大多数编译器都会为您这样做，因此无需让您的代码不可读

你的主要方法

public static void main(String[]args){
    int divisors = 0; //skip the = 0
    for(long x=1;divisors<=501;++x){ // ++x instead of x++
        divisors=0;
        long i=(x*x + x) >> 1; // see above, use the one you like more
        /*how many divisors*/
        if(i == 1) divisors = 1;
        else{ /*1 is the only number with just one natural divisor*/
            divisors = 2; // the 1 and itself
            for(int n = 2; n*n <= i; ++n){
                if(n*n == i) ++divisors;
                else if(i%n == 0) divisors += 2;
            }
        }
        System.out.println(i+": " + divisors);
    }
}

解释了++x而不是x++的事情here

多少除数部分： 除1外，每个数字至少有2个除数（素数、数字本身和1） 要检查一个数字有多少个除数，我们只需要找到这个数字的根 （例如36->；它的平方根是6） 36有9个除数（4对）{1和36，2和18，3和12，4和8，6（和6）}

1和36被跳过（for(**int n = 2**)），但被计入divisors = 2 pare2，3和4增加了2个除数 如果是一个平方数（n*n==i），那么我们加起来是1