我将如何加快这个程序？

Question

我目前正在尝试解决 ProjectEuler problem 问题，我已经解决了所有问题，除了速度。我几乎可以肯定程序执行如此缓慢的原因是嵌套循环造成的。我会喜欢一些关于如何加快速度的建议。我是一个新手程序员，所以很多更高级的我都不熟悉methods/topics.

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

Answer 2

您只需要对数字进行因式分解。 p^a * q^b * r^c 有 (a+1)*(b+1)*(c+1) 个除数。下面是使用这个想法的一些基本实现：

static int Divisors(int num) {
    if (num == 1) {
        return 1;
    }

    int root = (int) Math.sqrt(num);
    for (int x = 2; x <= root; x++) {
        if (num % x == 0) {
            int c = 0;
            do {
                ++c;
                num /= x;
            } while (num % x == 0);
            return (c + 1) * Divisors(num);
        }
    }

    return 2;
}

public static void test500() {
    int i = 1, num = 1;
    while (Divisors(num) <= 500) {
        num += ++i;
    }

    System.out.println("\nFound: [" + i + "] - " + num);
}

我将如何加快这个程序？

How would I speed up this program?

java

performance

loops

nested-loops