时间戳

首页 > 解决方案 > 第一个除以所有数字的数字 (1,2,...,100)

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

问题描述

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

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

  1. 我如何计算这是解决方案本身是一个无法处理的巨大数字？我尝试使用“BigInteger”，因为我做了很多加法和除法，但我不知道这是否会增加我的时间复杂度。

  2. 我怎样才能在不到一分钟的时间内计算出来？到目前为止，我认为的解决方案甚至还没有停止。

这是我的 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

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

还有其他想法吗？

标签： algorithmmathcalculatordivision

解决方案

可以除以某个集合的所有元素的第一个数字（这就是你所拥有的，尽管公式略有不同）也称为该集合的最小公倍数。LCM(a, b, c) = LCM(LCM(a, b), c)依此类推，所以一般来说，它可以通过取n - 1 个成对的 LCM 来计算，其中n是集合中的项目数。BigInteger没有lcm函数，但 LCM 可以通过a * b / gcd(a, b)Java 中的 so计算BigInteger：

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

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

推荐阅读