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

Метод 1: грубая сила
Метод грубой силы включает итерацию от 2 до квадратного корня заданного числа и проверку, является ли каждое число множителем. Если число является делителем, мы делим данное число на этот делитель до тех пор, пока оно не перестанет делиться. Вот код:

function findPrimeFactorsBruteForce(number) {
  let factors = [];
  for (let i = 2; i <= Math.sqrt(number); i++) {
    while (number % i === 0) {
      factors.push(i);
      number /= i;
    }
  }
  if (number > 1) {
    factors.push(number);
  }
  return factors;
}

Метод 2: Решето Эратосфена
Решето Эратосфена — это оптимизированный алгоритм для поиска всех простых чисел до заданного предела. Немного изменив этот алгоритм, мы также можем эффективно находить простые множители числа. Вот код:

function findPrimeFactorsSieve(number) {
  let factors = [];
  let sieve = new Array(number + 1).fill(true);
  for (let i = 2; i <= Math.sqrt(number); i++) {
    if (sieve[i]) {
      while (number % i === 0) {
        factors.push(i);
        number /= i;
      }
      for (let j = i * i; j <= number; j += i) {
        sieve[j] = false;
      }
    }
  }
  if (number > 1) {
    factors.push(number);
  }
  return factors;
}

Метод 3: алгоритм Ро Полларда
Алгоритм Ро Полларда — еще один эффективный метод поиска простых множителей числа. Он использует генератор случайных чисел и алгоритм поиска циклов для обнаружения факторов. Вот код:

function findPrimeFactorsPollardsRho(number) {
  if (number === 1) {
    return [];
  }
  if (isPrime(number)) {
    return [number];
  }
  let factors = [];
  while (number > 1) {
    let factor = pollardsRho(number);
    factors.push(factor);
    number /= factor;
  }
  return factors;
}
function pollardsRho(number) {
  let x = 2;
  let y = 2;
  let d = 1;
  let f = (n) => (x * x + 1) % n;
  while (d === 1) {
    x = f(x);
    y = f(f(y));
    d = gcd(Math.abs(x - y), number);
  }
  if (d === number) {
    return pollardsRho(number);
  }
  return d;
}
function gcd(a, b) {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

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