Как мне найти первое число, которое делится на первые 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

@ raulGLD Ваш код работает нормально, но не оптимизирован ,

Вы можете разорвать внутренний цикл после недопустимого условия
Также вы можете начать с 3 или 7 , так как [1,2,3,4,5,6 можно проверить с помощью [4,6,8,10,12]
- This необязательно, но перерыв важен

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