Как найти все делители числа при помощи Python
В математике часто требуется найти все делители заданного числа. В Python эта задача решается несколькими способами. В статье рассматриваются различные подходы, от самых простых до эффективных, с примерами кода и анализом производительности.
Эффективное решение с перебором до квадратного корня
Этот метод является наиболее сбалансированным по скорости и простоте.
def find_divisors(n):
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
return sorted(divisors)
print(find_divisors(36)) # [1, 2, 3, 4, 6, 9, 12, 18, 36]
делитель числа python (нахождение делителей числа в python)
Пояснение:
Алгоритм перебирает числа от 1 до sqrt(n). Если n делится на i, то i является делителем. Парный делитель n//i также добавляется, если он не равен i (для квадратов). В конце список сортируется.
Такой подход сокращает количество итераций с n до sqrt(n), что особенно важно для больших чисел.
Возможные проблемы:
- Для n=0 или отрицательных чисел код выдаст некорректный результат. Следует предусмотреть проверку: n должно быть натуральным числом.
- При очень больших n (например, 10^12) цикл все еще может быть медленным, но это уже физическое ограничение.
Как найти делители числа простым перебором от 1 до n?
def divisors_brute(n):
result = []
for i in range(1, n+1):
if n % i == 0:
result.append(i)
return result
print(divisors_brute(12)) # [1, 2, 3, 4, 6, 12]
Этот метод интуитивно понятен, но крайне неэффективен для больших n. Используется только для обучения или когда n заведомо мало (например, до 1000).
Главная ошибка: забыть включить само число n в диапазон. Начинать следует с 1.
Как компактно записать поиск делителей с помощью генератора списка?
def divisors_comprehension(n):
return [i for i in range(1, n+1) if n % i == 0]
print(divisors_comprehension(25)) # [1, 5, 25]
Генератор списка делает код лаконичным, но производительность такая же, как у простого цикла. Подходит для быстрого написания скрипта.
Как применить библиотеку numpy для нахождения делителей?
import numpy as np
def divisors_numpy(n):
candidates = np.arange(1, n+1)
mask = n % candidates == 0
return candidates[mask].tolist()
print(divisors_numpy(30)) # [1, 2, 3, 5, 6, 10, 15, 30]
numpy позволяет векторизовать проверку, что может ускорить работу на больших массивах, но для одиночного числа накладные расходы на создание массива перевешивают выгоду. Применяется при пакетной обработке множества чисел.
Требуется установленная библиотека numpy. Для чисел больше 10^6 может потребоваться много памяти.
Как использовать готовую функцию из библиотеки sympy?
from sympy import divisors
print(divisors(60)) # [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
sympy предоставляет оптимизированную реализацию, которая возвращает отсортированный список делителей. Это самый простой способ, если библиотека уже установлена. Подходит для научных расчетов.
sympy не входит в стандартную библиотеку Python, требуется установка через pip. Функция может быть медленнее самописной оптимизированной версии для очень больших чисел из-за дополнительной обработки.
Как найти делители числа рекурсивно?
def divisors_recursive(n, i=1, res=None):
if res is None:
res = []
if i > n:
return res
if n % i == 0:
res.append(i)
return divisors_recursive(n, i+1, res)
print(divisors_recursive(18)) # [1, 2, 3, 6, 9, 18]
Рекурсия демонстрирует другой подход, но для больших n может вызвать переполнение стека. Используется в учебных целях для иллюстрации рекурсивных алгоритмов.
Расширенные примеры
Пример 1: Сумма делителей и проверка совершенного числа
def sum_divisors(n):
total = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
total += i
if i != n // i:
total += n // i
return total
def is_perfect(n):
return sum_divisors(n) - n == n
print(is_perfect(28))
print(is_perfect(6))
print(is_perfect(496))
True True True
Пример 2: Использование множества для устранения дублирования
def divisors_set(n):
divs = set()
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divs.add(i)
divs.add(n // i)
return sorted(list(divs))
print(divisors_set(16))
[1, 2, 4, 8, 16]
Пример 3: Сравнение времени выполнения для числа 10^7
import time
def time_it(func, n):
start = time.perf_counter()
func(n)
end = time.perf_counter()
return end - start
def brute(n):
return [i for i in range(1, n+1) if n % i == 0]
def optimized(n):
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
return sorted(divisors)
n = 10_000_000
print('Brute:', time_it(brute, n))
print('Optimized:', time_it(optimized, n))
Brute: 2.34 Optimized: 0.0003
Пояснение:
Оптимизированный метод работает в тысячи раз быстрее.
Пример 4: Потоковый генератор делителей (экономия памяти)
def divisor_generator(n):
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
yield i
if i != n // i:
yield n // i
for d in divisor_generator(36):
print(d, end=' ')
1 36 2 18 3 12 4 9 6
Пример 5: Нахождение делителей с помощью multiprocessing (для очень больших чисел)
from multiprocessing import Pool
import math
def worker(start_end):
start, end, n = start_end
res = []
for i in range(start, end+1):
if n % i == 0:
res.append(i)
return res
def divisors_parallel(n, num_processes=4):
step = int(math.sqrt(n)) // num_processes
ranges = []
for i in range(num_processes):
start = i * step + 1
end = (i+1) * step if i != num_processes-1 else int(math.sqrt(n))
ranges.append((start, end, n))
with Pool(num_processes) as p:
results = p.map(worker, ranges)
divs = set()
for part in results:
for d in part:
divs.add(d)
divs.add(n // d)
return sorted(divs)
print(divisors_parallel(100))
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Примечание:
Параллельная версия имеет смысл только для очень больших чисел (10^12 и выше), когда выигрыш от многоядерности перевешивает накладные расходы на создание процессов.