我如何加快这个计划？

Question

我目前正在尝试解决ProjectEuler问题,除了速度之外,我已经解决了所有问题.我几乎可以肯定程序执行速度这么慢的原因是由于嵌套循环.我会喜欢一些关于如何提高速度的建议.我是一名新手程序员,所以我不熟悉很多更高级的方法/主题.

public class Problem12 {

    public static void main(String[] args) {
        int num;

        for (int i = 1; i < 15000; i++) {
            num = i * (i + 1) / 2;
            int counter = 0;

            for (int x = 1; x <= num; x++) {
                if (num % x == 0) {
                    counter++;
                }
            }
            System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers.");
        }
    }
}

编辑:下面是指数速度快的新代码.删除了恒定行打印以加快速度.

public class Problem12 {

    public static void main(String[] args) {
        int num;

        outerloop:
        for (int i = 1; i < 25000; i++) {
            num = i * (i + 1) / 2;
            int counter = 0;

            double root = Math.sqrt(num);
            for (int x = 1; x < root; x++) {
                if (num % x == 0) {
                    counter += 2;
                    if (counter >= 500) {
                        System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers.");
                        break outerloop;
                    }
                }
            }
        }
    }
}

Answer 1

对于初学者来说,在查看除数时,你永远不需要超过数字的根平方,因为平方根下面的每个除数都等于上面的等价.

n = a * b => a <= sqrt(n) or b <= sqrt(n)

然后你需要计算分裂的另一面:

double root = Math.sqrt(num);
for (int x = 1; x < root; x++) {
    if (num % x == 0) {
        counter += 2;
    }
}

平方根是特殊的,因为如果它是整数,它只计算一次:

if ((double) ((int) root) == root) {
    counter += 1;
}