Разработать функцию, которая для заданного натурального числа N возвращает количество его делителей
Возникла проблема с заданием, не могу найти ошибку: Разработать функцию, которая для заданного натурального числа N возвращает количество его делителей. С помощью данной функции: для заданного числа А вывести на экран следующее по отношению к нему число, имеющее столько же делителей, сколько и число А.
Например, если ввести число 4, то должно вывести 6, но не ничего не выводится
Для 4 следующее будет 9, т.к. у 6 четыре делителя, а нечётное количество — только у квадратов
Ошибки:
— i нужно было увеличивать в любом случае
— функция должна возвращать результат
— инкремент b+=1,а не b=+1
Всё ещё ищете ответ? Посмотрите другие вопросы с метками python или задайте свой вопрос.
Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.6.10.42345
Нажимая «Принять все файлы cookie», вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Напишите функцию которая возвращает количество делителей натурального числа
адача 20. Количество делителей. Составить рекурсивную программу-функцию подсчета количества всех положительных делителей натурального числа n.
Решение. Перейдем к более общей задаче. Подсчитаем для натурального числа n количества всех его положительных делителей, меньших или равных заданному натуральному числу x. Пусть dn(n) и dnx(n,x) — соответственно функции для решения исходной и обобщенной задач. Очевидно, что dn(n)=dnx(n,n).
Рекурсивную функцию dn x (n,x), по которой последовательно подвергаются испытанию на делители n все числа от 1 до x включительно, можно определить так:
Трудоемкость вычислений алгоритма решения задачи с использованием функции dn(n ) составляет O(n ) арифметических операций. Более эффективно эти вычисления можно проводить с помощью пары функций:
Рекурсивная функция dnx2(n,x ) аналогична функции dnx(n,x ), но подсчитывает удвоенное количество делителей n , не превосходящих x.
Функция dns(n), организуя выбор величины x, обращается к dnx2(n,x) соответственно с x=sq — 1 или с x=sq в зависимости от того, является ли n полным квадратом или нет. Этим и обеспечивается правильный учет количества положительных делителей n. Трудоемкость вычислений по dns(n ) составляет арифметических операций.
Контрольные примеры:
Заметим, что если n ³ 2 и d ns (n)=2, то число n – простое. Однако проверка n на простоту этим способом весьма неэкономна.
адача 21. Делители натурального числа. Составить рекурсивную программу-функцию, возвращающую все положительные делители натурального числа n.
Решение. Самый простой способ найти все положительные делители натурального числа n — это непосредственно проверить по очереди делимость n на каждое из чисел: 2, 3, …, n . Однако при таком подходе будет совершено достаточно много лишней работы. Например, ясно, что в промежутке от floor(n /2)+1 до n- 1 делители n отсутствуют.
Нам удобнее перейти к рассмотрению более общей задачи — нахождению делителей числа n в промежутке [ d,g ], где d и g — натуральные числа и (1 £ d £ g £ n ). Пусть div(n,d,g) — программа-функция решения этой вспомогательной задачи. При построении div(n,d,g ) параметры d и g будем менять, исходя из того, что для каждого делителя d числа n такого, что d × d £ n величина g=n/d также является делителем n и g × g ³ n . Решение исходной задачи можно будет получать обращением к div(n,1,n ) или с помощью функции divi(n ), в которой начальные значения d и g определяются автоматически:
Контрольный пример:
Обратите внимание на тот факт, что по функции div(n,d,g ) делители n всегда возвращаются в порядке возрастания. Это обеспечивается специальной организацией рекурсивных вычислений. А именно: после нахождения пары делителей d (d × d £ n ) и g (g × g ³ n ) первый сразу выводится в стек (вектор), а второй заносится туда лишь при отложенных вычислениях после выполнения соответствующего рекурсивного обращения.
Нахождение делителей числа с помощью 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.
Переход от факторизации к делителям
Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации: