第一个除以所有数字 (1,2,...,100) 的数字

Question

假设第一个整除所有 (1,2,..,10) 的数是 2520。假设第一个除以所有 (1,2,..,20) 的数字是 232792560。找到第一个除以所有 (1,2,..,100) 的数字。（从 1 到 100 的所有连续数字）。答案应该运行不到一分钟。

我正在 Java 中编写解决方案，我面临两个问题：

我如何计算这个解本身是一个大到无法处理的数字？我尝试通过进行许多加法和除法来使用“BigInteger”，但我不知道这是否会增加我的时间复杂度。
我怎样才能在不到一分钟的时间内完成计算？到目前为止，我想到的解决方案甚至还没有停止。

这是我的 Java 代码（使用大整数）：

public static boolean solved(int start, int end, BigInteger answer) {
    for (int i=start; i<=end; i++) {
        if (answer.mod(new BigInteger(valueOf(i))).compareTo(new BigInteger(valueOf(0)))==0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    BigInteger answer = new BigInteger("232792560");
    BigInteger y = new BigInteger("232792560");
    while(!solved(21,100, answer)) {
        answer = answer.add(y);
    }
    System.out.println(answer);
}

我利用了我已经知道 (1,..,20) 的解决方案这一事实。

目前根本停不下来

虽然我可以通过更改函数 solved 以仅检查我们关心的值来改进它。

For example:
100 = 25,50,100
99  = 33,99
98 = 49,98
97 = 97
96 = 24,32,48,96

等等。但是，这种识别所需最小数字组的简单计算本身已成为我没有寻找/找到解决方案的问题。当然，无论哪种情况，时间复杂度都应该控制在一分钟以内。

还有其他想法吗？

Answer 1

可以除以某个集合的所有元素的第一个数字（尽管公式略有不同，这就是你所拥有的）也被称为该集合的 Least Common Multiple。 LCM(a, b, c) = LCM(LCM(a, b), c) 等等，所以一般来说，可以通过取 n - 1 对 LCM 来计算，其中 n 是集合中的项目。 BigInteger 没有 lcm 函数，但可以通过 a * b / gcd(a, b) 计算 LCM，因此在 Java 中使用 BigInteger:

static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}

对于 1 到 20，以这种方式计算 LCM 确实会得到 232792560。也很容易达到 100。

Answer 2

找到你范围内的所有最大素数幂并取其乘积。

例如1-10: 2^3, 3^2, 5^1, 7^1: 乘积是 2520，这是正确答案（不是 5250）。您可以通过埃拉托色尼筛法找到素数，或者直接从素数列表中下载它们。

Answer 3

由于 100 很小，您可以通过对 2 到 100 之间的所有数字进行质因数分解并在所有因式分解中保留每个质数的最大指数来解决这个问题。事实上，尝试除以 2、3、5 和 7 就足以检查 100 以内的素数，而且只需要考虑 25 个素数。您可以实现一个简单的筛子来查找素数并执行因式分解。

找到 lcm 素数分解的所有指数后，您可以将其保留为答案，也可以明确地执行乘法。

第一个除以所有数字 (1,2,...,100) 的数字

First number that divides all numbers (1,2,...,100)

algorithm

math

calculator

division