Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Питон. Как найти все делители числа?

Скин Стим Профи (581), закрыт 1 год назад
Я знаю, что обычно перебор делителя делают до корня самого числа. Но, почему так делают и как правильно это организовать?
Лучший ответ
Ксения Райт Высший разум (105715) 1 год назад
Такой метод поиска натуральный делителей сам по себе довольно слабый в алгоритмическом отношении и достаточно малоэффективный на больших числах. Запускаем программу и смотрим что получается:
 from math import sqrt 
from time import time
while True:
n, d, t = int(input('n: ')), [], time()
m = int(sqrt(n))
if n == 1:
d = [1]
else:
for i in range(1, m + 1):
if n % i == 0:
d.append(i)
d.append(n // i)
if m * m == n:
d.remove(m)
d.sort()
for i in range(len(d)):
print('%4d) ' % (i + 1), d[i])
print(time() - t)
Без печати всего списка делителей вот за какие времена (в секундах) выполняется вычисление этих списков дроидом (смартфонным Пайтоном):Уже для n=1000000000000 время получается около секунды, что довольно много, и поэтому есть смысл весь алгоритм тупого перебора потенциальных делителей от 1 до ✓n поменять на более умный. Например, можно один раз вычислить список простых чисел, например, от 1 до миллиарда, а уж дальше числа n до квинтиллиона включительно факторизовать при помощи найденного списка простых чисел, что окажется неимоверно быстрее чем простой перебор, реализованный в вышеприведённой программе, а список всех делителей чисел дальше будет получаться автоматически. Если исследуемое на делители целое число меньше, допустим ста миллиардов, то и смысл в оптимизациях как-то сразу отпадает.
Кстати, если речь идёт о всех делителях чисел, тогда отрицательные делители тоже надо учитывать!
Остальные ответы
Doctor Strange Мыслитель (8012) 1 год назад
Это делают из за скорости, дальше корня нет смысла перебирать
Celtic Hammer Мудрец (17267) 1 год назад
Почему "до корня"? Потому что после корня по всем законам математики делителей больше не будет
VitnessПросветленный (35240) 1 год назад
Ну делители то после корня никуда не денутся.. Просто мы их уже найдем
⭐ МИНИСТРЕЛИЯ ⭐ Профи (916) 1 год назад
Для нахождения всех делителей числа важно понять, что делители расположены парами. Каждое число a имеет пару-делитель b, такой что b = a / b. Если b является делителем числа a, то a / b также будет делителем a. Если мы перебираем делители до корня числа a, то мы найдем все пары делителей и избежим повторений.

Для организации такого перебора в Python, можно использовать цикл for и проверять остаток от деления числа a на значения b в диапазоне от 1 до корня a. Если остаток равен нулю, то b является делителем a, и мы можем добавить b и a / b в список делителей.

 import math 

def find_divisors(a):
divisors = []
for b in range(1, int(math.sqrt(a)) + 1):
if a % b == 0:
divisors.append(b)
if b != a // b:
divisors.append(a // b)
return divisors

# Пример использования
number = 24
divisors = find_divisors(number)
print(divisors)
Похожие вопросы