Java中的Euler #5项目

Question

Euler项目5：

2520是最小的数，可以除以从1到10的每一个数，没有任何余数。什么是最小的正数，可以被从1到20的所有数字整除？

这是我的解决方案：

class SmallestMultiple {
    
    private static final int MAX = 20;

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = 1;
        for(int i = 1; i <= MAX; i++) {
            result = smallestMultiple(result, i);
        }
        time = System.nanoTime() - time;
        System.out.println("Result: " + result + "\nTime used to calculate in nanoseconds: " + time);
    }

    private static int smallestMultiple(int i, int j) {
        for(int index = 2; index <= i && index <= j; index++) {
            if(i % index == 0 && j % index == 0) {
                i /= index;
            }
        }
        return i * j;
    }

}

输出：

结果:以纳秒为单位计算的232792560 时间: 11603

问题：

1. 是最有效的吗？如果没有，我又如何改善呢？
2. 闻起来了吗？

Answer 1

优化1

你可以利用这样的事实：

 smallestMultiple(a, b) = a * b / gcd(a, b)

您可以通过gcd高效地计算欧几里得算法 (最大公因子)。

优化2

除此之外，如果你所说的“高效”指的是人类应该做最大可能的预处理，而不需要进行大量的计算，那么你可以通过知道最大发生的质数来快速地找到lcm(1, ..., 20)：

• 最大功率为2，即≤20: 16
• 最大功率为3，即≤20: 9。
• 最大功率为5，即≤20: 5。
• 最大功率为7，即≤20: 7。
• ..。
• 最大功率为19，即≤20: 19。

因此，通过以下方法可以最有效地计算lcm：

System.out.println(16*9*5*7*11*13*17*19);

请注意，这种“优化”假设人类已经知道20以下的素数，而不需要实际计算它们。;-)

Answer 2

在主循环中，与其从1开始，不如从result + 1开始。你也可以欺骗一点。由于从11到20的数字包含了从1到10的所有最大素数幂，所以实际上可以设置result = 11而不是1。

尽管问题中的目标范围为1-20，但int是足够大的，但请注意，进一步发展可能会导致result变量中的整数溢出。为了防止这种情况，您可能需要使用long来代替。

关于编码风格，变量名i和j最常用于循环，但在smallestMultiple中它们是方法参数，读取起来可能有点混乱。

在我的测试中，将smallestMultiple方法替换为@Legato中提到的lcm方法似乎要快一些。自从他删除了他的答案后，我就把它粘在这里(谢谢Legato!)：

/*Greatest Common Divisor
Euclidean algorithm: http://en.wikipedia.org/wiki/Euclidean_algorithm */
public static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b); 
}
// Least Common Multiple
public static long lcm(long a, long b) {
    return (a * b) / gcd(a, b);
}

Answer 3

我还建议您可以使用Java 8流来提高大量的性能。