Задача: Разложение числа на простые множители
Опубликован: 06.11.2024 47
Условие: напишите функцию разложения числа на простые множители, которая
получает целое число n и возвращает список простых множителей для этого числа.
Решение:
Алгоритм разложения числа на простые множители:
- Проверяем делимость числа
nна натуральные числа подряд, начиная с числа 2. - Если находим делитель числа
n, то делим числоnна этот делитель (пока число делится на него) и добавляем делитель в список простых множителей. - Если оставшееся после этого число
nбудет больше 1, то также добавляем его к списку простых делителей (т.к. это число тоже является простым).
def prime_factors(n):
res = []
d = 2
while d * d <= n:
if n % d == 0:
res.append(d)
n //= d
else:
d += 1
if n > 1:
res.append(n)
return res
n = 13195
print(prime_factors(n))
# [5, 7, 13, 29]
Похожие посты
Задача: Решение квадратного уравнения
Задача: Тренажер таблицы умножения
Задача: Наибольший числовой палиндром
Задача: Наибольший общий делитель
Комментариев нет.
Блог о трюках Python
Особенности самого популярного языка программирования Python
(трюки, лайфхаки, полезные приемы и хитрости кода)
Список категорий
Последние посты
- Задача: Решение квадратного уравнения
- Задача: Тренажер таблицы умножения
- Задача: Наибольший числовой палиндром
- Задача: Разложение числа на простые множители
- Задача: Наибольший общий делитель