Нахождение наименьшего общего кратного (НОК) двух или более чисел — распространенная задача в математике и информатике. В этой статье блога мы рассмотрим несколько методов расчета LCM с использованием JavaScript. Мы предоставим примеры кода для каждого подхода и обсудим их плюсы и минусы. Давайте погрузимся!

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

function findLCMBruteForce(numbers) {
  const maxNumber = Math.max(...numbers);
  let lcm = maxNumber;
  while (true) {
    if (numbers.every(number => lcm % number === 0)) {
      return lcm;
    }
    lcm += maxNumber;
  }
}
const numbers = [4, 6, 8];
const lcm = findLCMBruteForce(numbers);
console.log(`LCM: ${lcm}`);

Метод 2: подход наибольшего общего делителя (НОД)
НОК можно рассчитать, используя соотношение между НОД и НОД двух чисел. Мы можем использовать алгоритм Евклида, чтобы найти НОД, а затем вычислить НОК по этой формуле: НОК(a, b) = (a * b) / НОД(a, b). Вот код:

function findGCD(a, b) {
  if (b === 0) {
    return a;
  }
  return findGCD(b, a % b);
}
function findLCMGCD(numbers) {
  let lcm = numbers[0];
  for (let i = 1; i < numbers.length; i++) {
    const currentNumber = numbers[i];
    const gcd = findGCD(lcm, currentNumber);
    lcm = (lcm * currentNumber) / gcd;
  }
  return lcm;
}
const numbers = [4, 6, 8];
const lcm = findLCMGCD(numbers);
console.log(`LCM: ${lcm}`);

Метод 3: подход к факторизации простых чисел
Подход к факторизации простых чисел включает в себя нахождение простых множителей каждого числа и умножение наибольшей степени каждого множителя для расчета НОК. Вот код:

function getPrimeFactors(number) {
  const factors = [];
  let divisor = 2;
  while (number >= 2) {
    if (number % divisor === 0) {
      factors.push(divisor);
      number /= divisor;
    } else {
      divisor++;
    }
  }
  return factors;
}
function findLCMPrimeFactorization(numbers) {
  const allFactors = [];
  const factorsMap = {};
  numbers.forEach(number => {
    const factors = getPrimeFactors(number);
    factors.forEach(factor => {
      if (!factorsMap[factor] || factorsMap[factor] < factors.filter(f => f === factor).length) {
        factorsMap[factor] = factors.filter(f => f === factor).length;
      }
    });
    allFactors.push(...factors);
  });
  const lcm = allFactors.reduce((acc, factor) => acc * factor, 1);
  return lcm;
}
const numbers = [4, 6, 8];
const lcm = findLCMPrimeFactorization(numbers);
console.log(`LCM: ${lcm}`);

В этой статье мы рассмотрели три различных метода поиска наименьшего общего кратного в JavaScript. Мы обсудили подход грубой силы, подход НОД и подход простой факторизации. Каждый метод имеет свои преимущества и недостатки, и выбор метода зависит от таких факторов, как размер входных чисел и требования к эффективности приложения. Понимая эти методы, вы будете лучше подготовлены к эффективному решению задач LCM в JavaScript.