Нахождение делителей числа с помощью Python
Вот проблема, которую я недавно пытался решить: дано целое число n, каковы все его делители?
Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.
В итоге я написал кое-что с помощью itertools, и в моем коде используется несколько интересных моментов из теории чисел. Я не знаю, буду ли я возвращаться к нему снова, но я надумал написать эту статью, потому что мои попытки решить озвученный выше вопрос перетекли в довольно забавное упражнение.
Простейший подход
Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:
def get_all_divisors_brute(n): for i in range(1, int(n / 2) + 1): if n % i == 0: yield i yield 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:
def get_prime_divisors(n): i = 2 while i * i 1: yield nЭто похоже на предыдущую функцию, использующую перебор делителей: мы продолжаем пробовать множители, и если находим подходящий, то делим на него. В противном случае мы проверяем следующее число. Это довольно стандартный подход к поиску простых множителей.
Теперь мы можем использовать этот метод для получения факторизации числа, то есть для его записи в виде произведения простых чисел. Например, факторизация числа 8! выглядит следующим образом:
8! = 2^7 × 3^2 × 5 × 7
Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.
В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его в виде произведения простых множителей. (Я не буду приводить здесь доказательство, но вы можете найти его в Википедии).
Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.
Переход от факторизации к делителям
Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:
import collections def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) .Затем, давайте продолжим и возведем каждое простое число во все степени, которые могут появиться в возможном делителе n.
def get_all_divisors(n): . divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ]Например, для 8! представленный код выдаст нам следующее:
[ [1, 2, 4, 8, 16, 32, 64, 128], // 2^0, 2^1, . 2^7 [1, 3, 9], // 3^0, 3^1, 3^2 [1, 5], [1, 7], ]Затем, чтобы получить делители, мы можем использовать довольно удобную функцию itertools.product, которая принимает на вход итерабельные объекты и возвращает все возможные упорядоченные комбинации их элементов. В нашем случае она выбирает по одному числу из каждого списка с возведениями в степень, а затем, перемножая их вместе, мы получаем очередной делитель n.
import itertools def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): . for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination)Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).
Собираем все вместе
Сложив все это, мы получим следующую функцию для вычисления делителей n:
import collections import itertools def get_prime_divisors(n): i = 2 while i * i 1: yield n def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ] for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination) print(list(get_all_divisors(40320))) # 8!Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.
Как узнать количество делителей числа python
23. Цикл while. Нахождение всех делителей числа
24. Цикл while. Инструкции break, continue, else
25. Функция range и итерируемые объекты
26. Цикл for. Обход элементов функции range
27. Цикл for. Обход списков и строк
28. Установка, настройка и использование PyCharm
29. Метод подсчета. Сортировка подсчетом Python
30. Вложенные циклы
31. Вложенные списки
Видео доступно только для спонсоров проекта
Посмотреть данное видео на Boosty на Patreon
Оформить спонсорскую подписку можно на Youtube Boosty Patreon
Цикл while. Нахождение всех делителей числа
В самом простом случаем для поиска всех делителей для числа n нужно обойти все числа в интервале от 1 до n и проверить каждое число, является ли оно делителем. Код такой программы представлен ниже:
Но количество повторений цикла в этой программе напрямую зависит от переменной n и если ввести достаточно большое число, программе потребуется много времени на выполнение.
Мы можем повысить эффективность этой программы. Для этого нужно понимать, что самым большим делителем у любого числа является само это число. А вторым по старшинству делителем для четных чисел будет половина нашего исходного числа, а для нечетных - еще меньше чем половина. Значит мы можем искать делители в цикле на интервале от 1 до n//2 и после цикла выводить само число.
Эффективность этой программы увеличилась в 2 раза, но все же при вводе больших значений, программа будет долго работать.
Поэтому мы напишем ее следующим образом. Если мы знаем один делитель числа, то с легкостью можем найти второй делитель. Например, если мы знаем, что 2 является делителем числа 50, то деля 50 на 2, получаем еще один делитель 25. Значит мы можем искать предполагаемый первый делитель на интервале от 1 до корень из n (подробности в видео).
Нахождение делителей числа?
короче нужен эффективный алгоритм нахождения количества делителей числа. подскажите как это сделать?
- Вопрос задан более трёх лет назад
- 5853 просмотра
2 комментария
Средний 2 комментария
Эффективный по памяти или по времени?
Подробнее в Википедии
alex_643 @alex_643 Автор вопроса
Матвей Истомин, по времени
Решения вопроса 1
Здравствуйте!Есть идеи для такого алгоритма,можно идти до корня числа и проверять делится ли число,если делится - то сразу добавляем 2(т.к если 24 кратно 4,то оно и кратно 24/4),надо только проверить,если делитель * делитель не равно числу.
Вот реализация
while
def fact(a): i = 1 o = 0 while i * i Ответ написан более трёх лет назад
Комментировать
Нравится 1 Комментировать
Нахождение количества делителей и их сумму для вводимого числа по формулам
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n).
Входные данные
Дано натуральное n≤109.
Выходные данные
Выведите σ0(n) и σ1(n).
Знаю, что можно решить проще, без затрагивания темы простых делителей. Но на курсе в сириусе даются именно эти формулы:
0) n=p1^α1 * p2^α2 *. ps^as , где p1 1) σ0(n)=(α1+1)(α2+1). (αs+1).
2)σ1(n)=(1+p1+p1^2+. +p1^a1)(1+p2+. +p2^α2). (1+ps+. +ps^αs)
Код рабочий. По крайней мере Сириус высказал возмущение не к неисправности, а к высокой длительности. Как ускорить алгоритм?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
def is_Prime(n): if n 2: return False for divider in range(2, int(n ** 0.5 + 1)): if n % divider == 0: return False return True def get_list_of_prime_number(Number): list0 = [] for divider in range(2, Number + 1): if is_Prime(divider): list0.append(divider) return list0 N = int(input()) list_of_prime_number_for_N = get_list_of_prime_number(N) #создали список простых чисел числа N list_of_power_of_prime_number = [0 for _ in range(len(list_of_prime_number_for_N))]# создаём список из степеней простых чисел, образующих в случае умножения N power = 0 # будет работать как ссылка на степень из списка степеней всех простых делителей числа N for prime_number in list_of_prime_number_for_N: #читать после строки 27: а потом переходим к большему простому делителю while N % prime_number == 0:#Если число N делится на простое число не превышающее само N, тоесть является его делителем N //= prime_number # то делим list_of_power_of_prime_number[power] += 1 # и записываем сколько раз делится, тоесть степень power += 1 g0 = 1 for p in list_of_power_of_prime_number: # По формуле 1 для степеней простых делителей g0 *= (p + 1) #вычисляем количсетво делителей g1 = 1 i = 0 #итерируемая переменная for p in list_of_prime_number_for_N: # sum = 0 # for power in range(list_of_power_of_prime_number[i] + 1): # по формуле 2 находим одну скобку, состоящую из sum += p ** power #сумм одного простого делителя в степени от 0 до той которую применяет в формле 0 i += 1 g1 *= sum print(g0, g1)
Добавлено через 42 минуты
Пришла идея вместо функций использовать решето Эратосфена. Мне кажется, что я некорректно вшил его в код. Но не смотря на это мои простенькие примеры, он решал достаточно быстро, и вполне корректно. Сдал Сириусе, теперь не жалуется на длительность, говорит, что алгоритм выдаёт неправильные ответы. Сам код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
def get_list_of_prime_number(n): prime = [True] * (n + 1) prime[0] = prime[1] = False for i in range(2, n + 1): if not prime[i]: continue for j in range(i*i, n + 1, i): prime[j] = False list0 = [] for i in range(int(len(prime)//2 + 1)): if prime[i]: list0.append(i) return list0 N =int(input()) list_of_prime_number_for_N = get_list_of_prime_number(N) #создали список простых чисел числа N list_of_power_of_prime_number = [0 for _ in range(len(list_of_prime_number_for_N))]# создаём список из степеней простых чисел, образующих в случае умножения N power = 0 # будет работать как ссылка на степень из списка степеней всех простых делителей числа N for prime_number in list_of_prime_number_for_N: #читать после строки 27: а потом переходим к большему простому делителю while N % prime_number == 0:#Если число N делится на простое число не превышающее само N, тоесть является его делителем N //= prime_number # то делим list_of_power_of_prime_number[power] += 1 # и записываем сколько раз делится, тоесть степень power += 1 g0 = 1 for p in list_of_power_of_prime_number: # По формуле 1 для степеней простых делителей g0 *= (p + 1) #вычисляем количество делителей g1 = 1 i = 0 #итерируемая переменная for p in list_of_prime_number_for_N: # sum = 0 # for power in range(list_of_power_of_prime_number[i] + 1): # по формуле 2 находим одну скобку, состоящую из sum += p ** power #сумм одного простого делителя в степени от 0 до той которую применяет в формуле 0 i += 1 g1 *= sum print(g0, g1)