Вернуть массив общих делителей для заданного массива

Question

Описание

У меня задача:

Сделайте функцию, которая параметром будет принимать массив чисел и возвращать массив общих делителей всех чисел из переданного массива.

Мой код следующий:

function devidersForArr([...m]) {
  let array = [];

  function dividers(n) {
    for (let i = 1; i <= n; i++) {
      if (m.every((v) => v % i === 0)) array.push(i);
    }
  }
  m.forEach((v, i, a) => (a[i] = dividers(v)));
  return array;
}
console.log(devidersForArr([8, 12, 16]));

Вопрос

Мне кажется, что я где-то допустил ошибку и результат неправильный. Можно ли упростить код? Пробовал разные варианты, но этот самый рабочий)

Answer 1

Перебираем числа от 1 до минимального (спасибо за подсказку @StanislavVolodarskiy) числа в массиве. Если все элементы массива делятся без остатка на эти числа, помещаем делители в результирующий массив. Предполагаем, что в массиве натуральные числа.

function dividersForArr(m) {
    const array = [], max = Math.min(...m);
    for (let i = 1; i <= max; i++) {
        if (m.every(x => x % i === 0)) array.push(i)
    }
    return array;
}

console.log(dividersForArr([8, 12, 16]));

Answer 2

Если какое-то число делит все элементы массива, то оно делит их наибольший общий делитель (НОД). И наоборот, любой делитель НОД делит каждое число массива. Так что первый шаг - вычислить НОД элементов массива.

Есть число n, требуется найти все его делители. Разобъём их на три группы: меньше √n, равно √n, больше √n. Каждый делитель из первой группы имеет пару в третьей, и наоборот. То есть достаточно отыскать делители первой группы, проверить корень, по первой группе восстановить делители из третьей.

Добавим к этому интерфейс командной строки и будет тестировать:

const gcd2 = (a, b) => {
    while (b > 0) {
        const r = a % b;
        a = b;
        b = r;
    }
    return a;
};

const gcd = a => a.reduce(gcd2, 0);

// integer y: y * y <= x < (y + 1) * (y + 1)
const isqrt = x => {
    const y = Math.floor(Math.sqrt(x));
    return (y * y > x) ? y - 1 : y;
};

// all divisors of n
const divisors = n => {
    const nsqrt = isqrt(n - 1) + 1;
    const divisors = [];

    // fill all divisors < square root
    for (let i = 1; i < nsqrt; ++i) {
        if (n % i === 0) {
            divisors.push(i);
        }
    }

    const k = divisors.length;

    // add square root if needed
    if (nsqrt * nsqrt === n) {
        divisors.push(nsqrt);
    }

    // fill all divisors > square root
    for (let i = k - 1; i >= 0; --i) {
        divisors.push(n / divisors[i]);
    }

    return divisors;
};

const common_divisors = a => divisors(gcd(a));

(() => {
    const a = process.argv.slice(2).map(w => parseInt(w));
    process.stdout.write(common_divisors(a).toString());
    process.stdout.write('\n');
})();

$ node common-divisors.js 8 12 16
1,2,4

Вычисление НОД не так интересно. Дальнейшие примеры я буду давать для массива из одного элемента, так как будто НОД уже вычислен. Максимальное точно представимое целое в JavaScript - 9007199254740991 (константа [Number.MAX_SAFE_INTEGER](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER)). На него и буду ориентироваться.

Самое большое представимое число. Одна секунда:

$ time node common-divisors.js 9007199254740991
1,6361,69431,20394401,441650591,129728784761,1416003655831,9007199254740991

real  0m0.779s
user  0m0.772s
sys   0m0.004s

Самое большое представимое простое число. Уложились в одну секунду:

$ time node common-divisors.js 9007199254740881
1,9007199254740881

real  0m0.793s
user  0m0.784s
sys   0m0.008s

Два самых больших последовательных простых, произведение которых ещё представимо. Они к тому же близнецы. Снова одна секунда:

$ time node common-divisors.js 9007195909437503
1,94906247,94906249,9007195909437503

real  0m0.794s
user  0m0.780s
sys   0m0.012s

Число с, вероятно, наибольшим количеством делителей (30720 штук). Вывод укорочен по понятным причинам:

$ time node common-divisors.js 7302006324653040
1,2,3, ... ,2434002108217680,3651003162326520,7302006324653040

real  0m0.734s
user  0m0.724s
sys   0m0.000s

Максимальная представимая степень двойки - 2⁵² (53 делителя):

$ time node common-divisors.js 4503599627370496
1,2,4, ... ,1125899906842624,2251799813685248,4503599627370496

real  0m0.594s
user  0m0.576s
sys   0m0.016s

P.S. Перечислять делители числа можно быстрее чем это делается здесь. Есть две причинам так не делать: решение сравнительно простое и его производительность (менее секунды для любых данных) кажется приемлемой.

БЛОГ НА HUSL

Вернуть массив общих делителей для заданного массива

Описание

Вопрос

Ответы (2 шт):