3 Главный приём — рекурсивное разложение на простые множители
Главный приём — рекурсивное разложение на простые множители
Идея: находим наименьший делитель числа (перебором от 2 до √x). Он обязательно простой — будь у него делитель поменьше, тот делил бы и x. Записываем этот множитель и рекурсивно раскладываем то, что осталось (x // i). Если делитель не нашёлся — число само простое, возвращаем его.
def p(x):
for i in range(2, int(x**0.5) + 1): # ищем наименьший делитель до корня
if x % i == 0:
return [i] + p(x // i) # i — простой; раскладываем остаток
return [x] # делителей нет — x само простоеФункция возвращает список простых множителей по возрастанию. Например:
p(12)→[2, 2, 3](12 = 2·2·3)p(2726730289)→[67, 40697467](произведение двух простых)p(97)→[97](само простое)
📌 Что даёт список множителей Из списка |