День! решая задачу пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [1,2,4,8], а не [2,2,2] — список делителей. Я переписал этот алгоритм наново, прошу «старших товарищей» подсказать как улучшить. Если есть время ))
def divisorss(n): from collections import Counter ls = get_ls(n) # for n=1568 -> ls = [2, 2, 2, 2, 2, 7, 7] pairs = dict(Counter(ls)) # from itertools import product, starmap from operator import mul from functools import reduce # список всех различных делитей числа bases = [b for b in pairs.keys()] # [2, 7] # список степеней, в которые возводятся уникальные делители для получения числа powers = [[i for i in range(k+1)] for k in pairs.values()] # генерирование всех наборов для получения делителей исходного числа multi = product(*powers) # сцепка списка оснований с возможными вариантами степеней wrk = (zip(bases,power) for power in multi) # наборы чисел, которые нужно перемножить для получения делителя rezzz = (starmap( pow, row) for row in wrk) # возвращение списка всех делителей return [reduce(mul,i) for i in rezzz]
например divisorss(1568) возвращает [1, 7, 49, 2, 14, 98, 4, 28, 196, 8, 56, 392, 16, 112, 784, 32, 224, 1568] Функция get_ls(n) дает соответственно список разложения числа на произведение делителей например такая:
Как найти все делители числа?
def get_ls(n): «»»Разложить число на множители»»» #result = [1] result = [] i = 2 while i*i 1: result.append(n) return result
что можно улучшить?
Ну например, что лучше — reduce из functools или accumulate из itertools. Ну и вообще по алгоритму. Понятно, что улучшения типа
return [reduce(mul,i) for i in (starmap(pow, row) for row in (zip(bases,power) for power in product(*powers)))]
Источник: ru.stackoverflow.com
Вывести делители чисел
Для каждого натурального числа в промежутке от M до N вывести все делители, кроме единицы и самого числа. Значения M и N вводятся с клавиатуры.
В цикле перебирать числа от m до n и проверять делимость каждого на натуральные числа от 2 до m div 2 (деление нацело на 2, так как максимальный целый делитель равен половине числа). Если число делится нацело на текущий делитель (не имеет остатка), то выводить делитель на экран. В конце каждой итерации цикла увеличивать m на единицу.
Программа на языке Паскаль:
var m, n, i: word; begin readln(m, n); while m
Пример работы программы:
100 121 100: 2 4 5 10 20 25 50 101: 102: 2 3 6 17 34 51 103: 104: 2 4 8 13 26 52 105: 3 5 7 15 21 35 106: 2 53 107: 108: 2 3 4 6 9 12 18 27 36 54 109: 110: 2 5 10 11 22 55 111: 3 37 112: 2 4 7 8 14 16 28 56 113: 114: 2 3 6 19 38 57 115: 5 23 116: 2 4 29 58 117: 3 9 13 39 118: 2 59 119: 7 17 120: 2 3 4 5 6 8 10 12 15 20 24 30 40 60 121: 11
Источник: pas1.ru
21 Цикл while. Нахождение всех делителей числа Python
Практика оптимального программирования. Поиск делителей числа
Гадание на кофейной гуще или на картах Таро? Может, на ромашке? Хотя лучше не доверять свои отношения цветку. Наша судьба — только в наших руках. А судьба чисел предопределена заранее.
Сегодня мы будем предсказывать их жизнь и судьбу по делителям. Но главная проблема — найти эти делители.
Постановка проблемы. Переборное решение
Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 50 арбузов? А что подумаете, если ваш учитель математики задаст найти число, у которого 50 делителей?
Поиск делителей в математике не самый сложный процесс. Есть разные способы: разложение на простые множители, обычный перебор и так далее. Сложность задания будет зависеть от самого числа. Довольно быстро получится найти делители числа 24 — число небольшое, красивое, удобное. Нахождение делителей числа 1234567 займет гораздо больше времени.
Я предлагаю включить компьютер, открыть среду разработки и заставить код сделать за нас всю работу.
Идея в следующем:
- Создадим список, в который мы сохраним все делители числа.
- С помощью цикла for переберем все числа из диапазона от 1 до самого числа.
- Если в переборе мы нашли такое число, которое является делителем исходного — остаток от деления будет равен 0 — сохраним это число в список.
В итоге мы получим список всех делителей исходного числа.
number = 1234567 dels = [] for i in range(1, number + 1): if number % i == 0: dels.append(i) print(dels) _____________________________________________________________________ Вывод: [1, 127, 9721, 1234567]
У этого метода есть очень большая проблема — время его работы.
Программа выполняет команды очень быстро, но не бесконечно быстро.
Время работы программы можно измерить. Например, Sublime Text 3 занимается этим автоматически. И он помог посчитать, что программа выше выполнилась за 0.2 секунды. Давайте постепенно повышать ставки и смотреть, сколько времени понадобится этой же программе для поиска делителей других чисел:
— число 1234567 — 0.2 секунды;
— число 12345670 — 0.9 секунды;
— число 123456700 — 8.0 секунд;
— число 1234567000 — 115.7 секунд.
Замеры времени зависят от многих факторов, например, мощности компьютера. Но мы можем повысить эффективность работы программы.
Ускоренный перебор делителей
Идея ускоренного перебора делителей заключается в том, что, найдя один делитель, мы сразу можем подобрать второй — его пару.
Возьмем число 24. Найдя его делитель 2, мы сразу можем сказать, что у 24 есть еще один делитель — 12, потому что 12 = 24 / 2. Интересная мысль? Давайте ее развивать.
Найдем по такой логике все делители числа 16.
- Самый простой делитель числа — 1. И по этой логике сразу найдем второй делитель — само число 16, так как 16 / 1 = 16.
- Проверим число 2. Это делитель, так что сразу найдем его пару: 16 / 2 = 8.
- Проверяем число 3 — это не делитель, его просто пропускаем.
- При проверке числа 4 мы столкнемся с интересной ситуацией. Его парой будет 16 / 4 = 4 — то же самое число, а мы ищем различные пары. Значит, у корня числа пары не будет: найдя корень, мы найдем только один делитель.
Если мы продолжим перебор, числа 5, 6 и 7 — не будут делителями. А за ними — 8, делитель, который мы уже нашли.
Если у числа целого корня нет, перебираем до его округленного вниз значения.
Нам нет смысла перебирать числа после корня, так что будем перебирать до предельно близкого к нему значения, но не больше.
Логика программы будет такой:
- Перебираем числа от 1 до корня исходного числа.
- Если мы нашли корень числа, добавляем в список делителей только его.
- Если мы нашли не корень, а обычный делитель — добавляем в список сразу пару делителей.
Пример реализации ускоренного перебора делителей для числа 1234567000:
number = 1234567000 dels = [] for i in range(1, int(number ** 0.5) + 1): if i * i == number: dels.append(i) elif number % i == 0: dels.append(i) dels.append(number // i) print(len(dels)) _____________________________________________________________________ Вывод: 64
Эта программа нашла все делители числа и выдала их количество — 64. А на ее работу ушло меньше секунды.
Но и это не панацея. Что, если нам придется проверить делители сразу нескольких чисел? Например, мы хотим найти все числа, у которых ровно 7 делителей, в диапазоне от 1 до 10000.
Программу надо немного модифицировать:
- заведем переменную-счетчик, которая будет считать подходящие числа;
- number сделаем перебираемой переменной по нужному диапазону с помощью цикла for;
- ускоренный перебор будет внутри перебора number;
- в конце каждого шага цикла проверяем — если делителей у числа ровно 7, то увеличиваем наш счетчик на 1.
Теперь программа будет выглядеть следующим образом:
count = 0 for number in range(1, 10000): dels = [] for i in range(1, int(number ** 0.5) + 1): if i * i == number: dels.append(i) elif number % i == 0: dels.append(i) dels.append(number // i) if len(dels) == 7: count += 1 print(count) _____________________________________________________________________ Вывод: 2
Эта программа работала всего 0.2 секунды. Звучит неплохо, но давайте снова поднимать ставки:
- диапазон 1 — 10000 — 0.2 секунды;
- диапазон 1 — 100000 — 2.6 секунды;
- диапазон 1 — 1000000 — 80.2 секунды.
Время снова увеличивается очень быстро. Что можно с этим сделать?
Еще более ускоренный перебор делителей
Не считаем, что не нужно
Обратите внимание — программа выше нашла среди чисел 1–10000 всего 2 числа, имеющих ровно 7 делителей. А сколько же у остальных? Может быть и больше, может быть и меньше. Например, у числа 9864 делителей аж 24 штуки. Стоило ли тратить время на поиск их всех, если количество делителей больше 7?
Конечно, нет. Как только мы нашли 8 штук, мы уже можем понять, что анализировать число далее нам неинтересно. Значит, нужно остановить работу цикла.
Команда break полностью останавливает работу цикла.