Поиск всех делителей числа: эффективные методы и реализация на Python
Основной эффективный алгоритм
Наиболее производительный способ нахождения всех делителей натурального числа n основан на переборе только до квадратного корня из n. Для каждого найденного делителя i добавляется парный делитель n // i. Это сокращает количество итераций с n до ~sqrt(n).
def find_divisors(n):
divisors = set()
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.add(i)
divisors.add(n // i)
return sorted(divisors)
поиск делителей числа python (поиск всех делителей числа в python)
Пояснение: цикл идет от 1 до sqrt(n) включительно. Если i делит n, то i и n//i являются делителями. Использование set позволяет избежать дубликатов (когда n - полный квадрат). После преобразуем в отсортированный список.
Типичные ошибки:
- Забыть учесть, что делители идут парами, и добавлять только i (получается только половина делителей).
- Использовать n**0.5 без преобразования в int, что приводит к ошибкам типа при больших числах (лучше использовать math.isqrt).
- Не обрабатывать случай n = 1 (цикл от 1 до 1, добавляет 1 и 1, set оставляет один).
Как получить все делители числа, перебирая каждое число от 1 до n?
Самый прямолинейный метод - проверять каждое число от 1 до n на делимость. Подходит только для небольших n.
def divisors_bruteforce(n):
return [i for i in range(1, n+1) if n % i == 0]
Проблемы:
- При n = 10^9 количество итераций неприемлемо.
- Неэффективно для больших чисел.
Как найти делители числа, используя разложение на простые множители?
Алгоритм основан на основной теореме арифметики: любое число раскладывается на простые множители, а все делители - это все возможные произведения подмножеств этих множителей. Требуется предварительная факторизация.
from collections import Counter
from functools import reduce
from itertools import product
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
while n % i == 0:
factors.append(i)
n //= i
i += 1 if i == 2 else 2
if n > 1:
factors.append(n)
return Counter(factors)
def divisors_from_factors(n):
counter = prime_factors(n)
powers = [[p**k for k in range(count+1)] for p, count in counter.items()]
all_combos = product(*powers)
divisors = [reduce(lambda x,y: x*y, combo) for combo in all_combos]
return sorted(divisors)
Сложности:
- Факторизация для больших чисел может быть медленной без дополнительных оптимизаций.
- Необходимость работы с комбинаторикой и reduce.
- Для чисел с большим количеством простых множителей количество делителей может быть огромным, и список может не поместиться в память.
Как найти делители числа с помощью готовой библиотеки sympy?
Библиотека sympy предоставляет функцию divisors, которая возвращает список всех делителей. Это самый простой способ, если допустимо использовать внешние зависимости.
from sympy import divisors
print(divisors(36)) # [1, 2, 3, 4, 6, 9, 12, 18, 36]
Недостатки:
- Требуется установка sympy (pip install sympy).
- Для очень больших чисел может быть неоптимальной по скорости (sympy использует разложение).
- Не подходит, если нужно контролировать процесс или изучать алгоритмы.
Дополнительные примеры и тонкости реализации
Рассмотрим более сложные сценарии и расширенные возможности.
Пример 1: Оптимизированная функция с использованием math.isqrt
import math
def divisors_optimized(n):
if n <= 0:
return []
result = set()
for i in range(1, math.isqrt(n) + 1):
if n % i == 0:
result.add(i)
result.add(n // i)
return sorted(result)
print(divisors_optimized(28))
print(divisors_optimized(100))
[1, 2, 4, 7, 14, 28] [1, 2, 4, 5, 10, 20, 25, 50, 100]
Здесь math.isqrt гарантирует целочисленный квадратный корень без ошибок округления.
Пример 2: Вычисление суммы делителей и их количества
import math
def divisor_stats(n):
total = 0
count = 0
for i in range(1, math.isqrt(n) + 1):
if n % i == 0:
total += i
count += 1
other = n // i
if other != i:
total += other
count += 1
return count, total
print(divisor_stats(12))
print(divisor_stats(36))
(6, 28) (9, 91)
Для 12 делители: 1,2,3,4,6,12 (6 штук, сумма 28).
Пример 3: Генерация делителей с помощью разложения на простые множители и itertools.product
from collections import Counter
from itertools import product
import math
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1 if d == 2 else 2
if n > 1:
factors.append(n)
return Counter(factors)
def divisors_by_factorization(n):
counter = prime_factors(n)
prime_powers = []
for prime, exp in counter.items():
powers = [prime**k for k in range(exp+1)]
prime_powers.append(powers)
for combo in product(*prime_powers):
yield math.prod(combo)
n = 72
print(sorted(divisors_by_factorization(n)))
[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
Функция-генератор позволяет обрабатывать делители по одному, экономя память. Обратите внимание на использование math.prod для произведения.