如何找到与前 20 个数字相除的第一个数字？

Question

我想找到可以在没有提醒的情况下除以前20个数字（1，2，3...20）的最小数字（我尝试过一些我认为不会失败的东西，就像这样：for (int i = 20; i < Integer.MAX_VALUE; i++) {    int seImparte = 0;    for (int j = 1; j <= 20; j++) {        if (i % j != 0) {            seImparte++;        }    }    if (seImparte == 0) {        System.out.println(i);        break;    }}我以为我会得到第一个数字，然后程序会退出，但它运行并且没有任何反应。感谢您的时间和帮助！

Answer 1

您可以在无效条件

之后中断内部循环，也可以从3或7开始，因为[1，2，3，4，5，6可以通过[4，6，8，10，12]进行测试 -

这是可选的，但中断很重要

     for (int i = 20; i < Integer.MAX_VALUE; i++) {

      int seImparte = 0;

        for (int j = 7; j <= 20; j++) {

            if (i % j != 0) {

                seImparte++; break;

            }

        }

        if (seImparte == 0) {

            System.out.println(i);

            break;

        }

    }

输出： 232792560

Answer 2

与其优化暴力破解方法，不如使用简单的数学规则。

由此产生的复杂性与“大量”相对应O(n*log(n))

Python 代码使用最小公用多重函数

def gcd(a, b):

    while b > 0:

        a, b = b, a % b

    return a

def lcm(a, b):

    return a * b // gcd(a, b)     # integer division

d = 1

for i in range(2, 21): #last i=20

    d = lcm(d, i)

print(d)

>>[Dbg]>>> 232792560

此外，我们可以将范围内的所有数字分解为素数，并记住每个素数的最大幂。在这种情况下：并乘以这些幂。更复杂的代码（但这种方式有时可能很有用）2:4; 3:2; 5:1; 7:1; 11:1; 13:1; 17:1; 19:1

232792560 = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19

Answer 3

希望这是你正在寻找的：

for (int i = 2; i < Integer.MAX_VALUE; i++) {

        for (int j = 2; j <= 20; j++) {

            if (i % j == 0) {

                System.out.println("i : "+i+" j : "+j);

                break;

            }

        }

    }