Как я могу эффективно получить все делители X в пределах диапазона, если у меня есть первичная факторизация X?
Итак, у меня есть алгоритмы (легко доступные для поиска в сети) для простой разложения и получения делителей, но я не знаю, как масштабировать их, чтобы найти эти делители в пределах диапазона. Например, все делители 100 между 23 и 49 (произвольно). Но также что-то эффективное, так что я могу масштабировать это до больших чисел в больших диапазонах. Сначала я думал об использовании массива размером с диапазон, а затем использовал все простые числа. <= верхняя граница для просеивания всех элементов в этом массиве, чтобы вернуть возможный список делителей, но для больших диапазонов это будет слишком много памяти.
Есть ли простой способ просто напрямую генерировать делители?
Решение
Позволять 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 немного сомнительны).
Другие решения
Поскольку Мальволио (косвенно) шел, я лично не нашел бы применение для простой факторизации, если вы хотите найти факторы в диапазоне, я бы начал с int t = (int) (sqrt (n)), а затем уменьшал до
1. это фактор
2. Полный диапазон использования или T / N был достигнут (флаг), а затем (оба) покинул диапазон
Или, если ваш диапазон относительно мал, проверьте сами эти значения.
Если вы знаете факторы N, Вы можете рассчитать делители N — эти цифры, в том числе 1 и N, что поровну N — принимая продукты powerset факторов 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
Получив полный список делителей, вы можете выбрать только те, которые находятся в требуемом диапазоне.