Как я могу эффективно получить все делители X в пределах диапазона, если у меня есть первичная факторизация X?

Question

Так что у меня есть алгоритмы (легко доступные для поиска в сети) для простого разложения на множители и получения делителей, но я не знаю, как его масштабировать, чтобы найти эти делители в пределах диапазона. Например, все делители 100 между 23 и 49 (произвольно). Но также что-то эффективное, чтобы я мог масштабировать это до больших чисел в больших диапазонах. Сначала я думал об использовании массива, который имеет размер диапазона, а затем использовал все простые числа <= верхнюю границу, чтобы просеять все элементы в этом массиве, чтобы вернуть возможный список делителей, но для больших диапазонов это было бы слишком интенсивная память.

Есть ли простой способ просто напрямую генерировать делители?

Answer 1

Позволять n[i] быть i-м фактором вашего числа x, i < m, Для любого целого числа j больше 1 и меньше чем 2^mтогда произведение всех n[j[r]] где j[r] это r-th немного j является делителем x,

Рассмотрим 105. Его факторы [3, 5, 7], Итак, 3 фактор, 2^3 - это 8:

 0  000                = 1
 1  001              7 = 7
 2  010          5     = 5
 3  011          5 * 7 = 35
 4  100      3         = 3
 5  101      3   *   7 = 21
 6  110      3 * 5     = 15
 7  111      3 * 5 * 7 = 105

Увидеть? Все возможные делители 105 (0 и 7 немного сомнительны).

Answer 2

Поскольку Мальволио (косвенно) шел, я лично не нашел бы применение для простой факторизации, если вы хотите найти факторы в диапазоне, я бы начал с int t = (int)(sqrt(n)) и затем уменьшал до
1. это фактор
2. Полный диапазон использования т или т / п был достигнут (флаг), а затем (оба) покинул диапазон

Или, если ваш диапазон относительно мал, проверьте сами эти значения.

Answer 3

Если вы знаете факторы n, вы можете вычислить делители n --- те числа, в том числе 1 и n, которые равномерно делят n ---, взяв произведения из набора степеней из факторов n:

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

Получив полный список делителей, вы можете выбрать только те, которые находятся в требуемом диапазоне.