алгоритм поиска всех делителей числа
День! решая задачу пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [1,2,4,8], а не [2,2,2] — список делителей. Я переписал этот алгоритм наново, прошу «старших товарищей» подсказать как улучшить. Если есть время ))
например divisorss(1568) возвращает [1, 7, 49, 2, 14, 98, 4, 28, 196, 8, 56, 392, 16, 112, 784, 32, 224, 1568]
Функция get_ls(n) дает соответственно список разложения числа на произведение делителей
что можно улучшить?
Ну например, что лучше — reduce из functools или accumulate из itertools. Ну и вообще по алгоритму.
Понятно, что улучшения типа
А если в одну строку через lambda-функцию:
Обновление, более громоздкий вариант:
Я бы нашел все делители вот так:
Сначала бы перебрал все числа от 1 до квадратного корня из числа, округленного в большую сторону. И записал бы в список все числа, на которые без остатка делится число. Это будет первая половина всех делителей.
Последующие числа я бы уже не проверял, а просто разделил число на все делители из первой половины и записал бы результаты в список. Это была бы вторая половина всех делителей. Единственный момент, если у чисeл квадратный корень — это целое число, то он попадет и в первый и во второй список, поэтому проверяю тут, каждое из числе уже не содержится в первом списке.
Возвращаем результирующий список (конкатенация первой и второй половины).
Нахождение делителей числа с помощью Python
Вот проблема, которую я недавно пытался решить: дано целое число n, каковы все его делители?
Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.
В итоге я написал кое-что с помощью itertools, и в моем коде используется несколько интересных моментов из теории чисел. Я не знаю, буду ли я возвращаться к нему снова, но я надумал написать эту статью, потому что мои попытки решить озвученный выше вопрос перетекли в довольно забавное упражнение.
Простейший подход
Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:
На деле нам нужно дойти только до n/2, потому что все, что больше этого значения, гарантировано не может быть делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.
Этот код очень прост, и для малых значений n он работает достаточно хорошо, но он довольно неэффективен и медлителен в других случаях. По мере увеличения n время выполнения линейно увеличивается. Можем ли мы сделать лучше?
Факторизация
В моем проекте я работал в основном с факториалами. Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
Поскольку факториалы состоят преимущественно из небольших множителей, я решил попробовать получить список делителей, определив сначала наименьшие из них. В частности, я искал простые множители, то есть те, которые также являются простыми числами. (Простое число — это число, единственными делителями которого являются оно само и 1. Например, 2, 3 и 5 являются простыми, а 4 и 6 — нет).
Вот функция, которая находит простые делители числа n:
Это похоже на предыдущую функцию, использующую перебор делителей: мы продолжаем пробовать множители, и если находим подходящий, то делим на него. В противном случае мы проверяем следующее число. Это довольно стандартный подход к поиску простых множителей.
Теперь мы можем использовать этот метод для получения факторизации числа, то есть для его записи в виде произведения простых чисел. Например, факторизация числа 8! выглядит следующим образом:
8! = 2^7 × 3^2 × 5 × 7
Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.
В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его в виде произведения простых множителей. (Я не буду приводить здесь доказательство, но вы можете найти его в Википедии).
Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.
Переход от факторизации к делителям
Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:
Как найти все делители числа python
Как найти все делители числа в Python
При работе с числами в Python часто требуется находить все делители заданного числа. Нахождение всех делителей может быть полезно для решения различных задач, таких как нахождение наибольшего общего делителя, проверка числа на простоту и т.д. В этой статье мы рассмотрим несколько способов нахождения всех делителей числа в Python.
Простой подход нахождения делителей
Простой подход заключается в переборе всех чисел от 1 до заданного числа n и проверке каждого числа на деление на n . Код для нахождения всех делителей числа n с помощью наивного подхода будет выглядеть следующим образом:
Этот код работает корректно и находит все делители заданного числа. Однако, его сложность времени составляет O(n), что может быть неприемлемо для больших чисел.
Более оптимальный подход нахождения делителей
Второй способ нахождения всех делителей заключается в переборе только чисел от 1 до корня из заданного числа n. Если мы нашли делитель i , то мы также можем добавить в список делителей n/i . Код для нахождения всех делителей числа n с помощью более оптимального подхода будет выглядеть следующим образом:
Этот код работает корректно и имеет сложность времени O(sqrt(n)) , что гораздо лучше, чем простой подход.
Решето Эратосфена в Python
Третий способ нахождения всех делителей заключается в нахождении всех простых делителей заданного числа и их степеней. Для нахождения простых делителей мы можем использовать Решето Эратосфена.
Затем мы будем проверять, на какие степени делятся каждый из простых делителей. Код для нахождения всех делителей числа n с помощью Решета Эратосфена будет выглядеть следующим образом:
Эти функции могут быть использованы для нахождения делителей любого целого числа. Например, для числа 12 результат работы этих функций будет таким:
Делители числа
Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.
Нахождение делителей числа
С практической точки зрения будет полезно, если программа на Python не только будет находить делители числа, искать их сумму, определять минимальный и максимальный, а также простые делители.
Каждая подзадача так или иначе связана с предыдущей, поэтому код последующей программы — это немного модернизированный код предыдущей. Кроме того, весь функционал при необходимости можно объединить в одной программе.
Пользователь вводит целое число, делителей которого будет искать программа, тогда код выглядит так:
Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:
Простые делители числа
Простой делитель — это делитель, который делится только на единицу и самого себя. Для нахождения простых делителей с помощью Python нужно немного модернизировать программу, добавив в неё дополнительный цикл for и переменную счётчик.
Программа построена по следующему алгоритму:
- Обнулить счётчик.
- В цикле искать делители.
- Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
- Если найден, увеличить счётчик.
- Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
- Перейти на следующую итерацию внешнего цикла.
Цикл теперь выглядит так:
Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.
Результат работы программы:
Делители расположены в порядке убывания. И если надо вывести только самый большой простой делитель с помощью Python, то можно после того, как выведется первое число, воспользоваться оператором break для выхода из цикла.
Сумма делителей
Для того чтобы найти сумму всех делителей числа с помощью Python, достаточно добавить в начальную программу переменную, к которой в цикле будет прибавляться каждый найденный делитель.
Код программы:
Результат выполнения кода:
Количество делителей
Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие « numb % i == 0 » будет выполняться.
Результаты выполнения программы:
Максимальный и минимальный делитель
Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider . В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.