НОК двух чисел в Java — программа через цикл while

Наименьшее общее кратное (НОК, англ. LCM) двух чисел — это самое маленькое положительное число, которое делится без остатка на оба числа. Например, НОК(72, 120) = 360.

Пример 1: НОК через цикл while и if

Простая идея: начать с большего из чисел и увеличивать значение на 1 до тех пор, пока оно не станет делиться на оба числа.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    int n1 = 72, n2 = 120;

    int gcd = findGCD(n1, n2);
    int lcm = (n1 * n2) / gcd;

    System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
  }

  public static int findGCD(int a, int b) {
    if (b == 0)
      return a;
    return findGCD(b, a % b);
  }
}

Вывод:

The LCM of 72 and 120 is 360.

В программе n1 и n2 — числа, для которых ищем НОК. Изначально lcm устанавливается равным большему из них, так как НОК не может быть меньше большего числа.

В бесконечном цикле while(true) мы проверяем, делится ли lcm нацело и на n1, и на n2. Если делится — НОК найден, выводим его и выходим из цикла с помощью break. Иначе увеличиваем lcm на 1 и проверяем снова.

Совет

НОК можно найти и через НОД по формуле LCM = (n1 * n2) / GCD.

Пример 2: НОК через НОД

В этом варианте мы используем рекурсивную функцию findGCD для вычисления НОД, а затем считаем НОК по формуле выше.

public class Main {
  public static void main(String[] args) {
    int n1 = 72, n2 = 120;

    int gcd = findGCD(n1, n2);
    int lcm = (n1 * n2) / gcd;

    System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
  }

  public static int findGCD(int a, int b) {
    if (b == 0)
      return a;
    return findGCD(b, a % b);
  }
}

Вывод этой программы такой же, как в Примере 1.

Здесь сначала вычисляется НОД двух чисел n1 и n2, после чего по формуле находится НОК.