如何加速这个程序？

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

- jzbakos

---

尝试使用更快的语言，比如C语言，并尝试在Java中使用位移操作代替除法和乘法，如果可用的话。 - Shahe Ansar

这个算法到底有用吗？比如如果 i=3，那么 num=6，然后 counter=4，这是不正确的。 - afsafzal

如果你不知道位移操作是否被支持，怎么能断言C比Java更快呢？ - njzk2

@afsafzal 你的意思是“哪个是正确的”。对于6，期望的值为1、2、3、6，正如OP链接中所述。 - njzk2

你将要打印15000行。任何打印操作比简单语句的执行时间都要长得多，因此如果你想计时，首先应该将打印操作注释掉。 - Mike Dunlavey

@njzk2 因为我使用过的每个Java应用程序都非常低效。 - Shahe Ansar

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

- njzk2

---

这个方法起作用了。但是我不确定为什么。您能否详细解释一下为什么它有效？ - jzbakos

每个除数都作为一对工作，这就是为什么我们要计算两次的原因。对于每一对，其中一个元素在平方根下面，另一个在上面。这很容易理解：如果两个元素都在上面，结果也在上面。如果两者都在下面，则结果也在下面。例如：10 = 2*5 = 1*10。2和1在3.16以下，5和10在上面。 - njzk2

虽然我错了，关于没有三角形和正方形数，现在正在编辑。 - njzk2

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

- Antonín Lejsek