Я огляделся и нашел другие вопросы, на которые были ответы, но ни один из них не затрагивает рамки этого конкретного вопроса, включая этот вопрос , а также этот .

Мне нужно эффективно вычислить НОК больших диапазонов чисел. Я не рассматривал -эти другие вопросы слишком глубоко, потому что они не имеют дело с диапазонами чисел, которые должны быть обработаны этим алгоритмом.

Код, который у меня есть сейчас, может вычислить LCM каждого числа от 1 до 350000 примерно за 90 секунд. (Полученное число состоит примерно из 76000 десятичных цифр ). Я надеюсь, что в конечном итоге смогу масштабировать его на диапазоны длиной в миллионы или даже миллиарды элементов.

Вероятно, в конечном итоге это будет распараллелено. Для некоторых алгоритмов это совсем несложно, для других это будет сложнее (, если, например, алгоритм использует текущий сгенерированный LCM для вычисления простоты для других частей своих вычислений )

. Вот он:

public static BigInteger getLCMOfRange(BigInteger lower, BigInteger upper)
{
    BigInteger M = BigInteger.ONE;
    BigInteger t;

    // long l = System.currentTimeMillis();
    // System.out.println("Calculating LCM of numbers up to " + upper + "...");
    for (; lower.compareTo(upper) != 1; lower = lower.add(BigInteger.ONE))
    {
        t = M.gcd(lower);
        if (t.compareTo(lower) == 0)
            continue;
        M = M.multiply(lower).divide(t);
    }
    // System.out.println("Done.  Took " + (System.currentTimeMillis() - l) + " milliseconds.  LCM is " + M.bitCount()+ " bits long.");
    return M;
}

Обратите внимание, что в отличие от типичного цикла for, эта функция работает с [нижний, верхний] вместо [нижний, верхний ). Такое поведение является преднамеренным.

Немного поддерживающей математики заключается в том, что НОК некоторого набора чисел является продуктом набора простых множителей, из которых можно получить любое из чисел, не требуя каких-либо внешних пулов. Если мой диапазон равен [1,20], я могу представить это следующим образом:

1: 1         6:  3*2      11: 11       16: 2^4
2: 2         7:  7        12: 3*2^2    17: 17
3: 3         8:  2^3      13: 13       18: 3^2*2
4: 2^2       9:  3^2      14: 7*2      19: 19
5: 5         10: 5*2      15: 5*3      20: 5*2^2

LCM{[1,20]}: 2^4*3^2*5*7*11*13*17*19 = 232792560

Существуют ли более эффективные способы вычисления LCM в таком большом диапазоне?

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

Это не вопрос домашнего задания.

Вопрос

Каков наиболее эффективный способ расчета НОК для очень большого диапазона чисел? Этот алгоритм должен работать с непомерно широким диапазоном чисел и поэтому должен быть тщательно оптимизирован.

Приложение 1

Тесно связанный с этим вопрос: :Каков наиболее эффективный способ вычисления логарифма одного BigInteger (по основанию другого BigInteger )? Полученное значение может быть усечено до ближайшего целого числа.