Задание 23. Информатика. ЕГЭ. Поляков-9040

(И. Карпачёв) У исполнителя имеются две команды, которые обозначены латинскими буквами:

1. Вычти \(1\)
2. Раздели на наименьший простой делитель

Первая из этих команд уменьшает число на экране на \(1.\) Вторая команда делит заменяет число на экране на его наименьший простой делитель. Эту команду можно применять только к составным числам, к простым числам и единице данная команда неприменима. Сколько существует команд, для которых при исходном числе \(150\) результатом является \(7?\)

from math import isqrt

def md(n):
    if n < 4:
        return 0
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return d
    return 0

def f(n, targ):
    if n <= targ:
        return n == targ
    return f(n - 1, targ) + (f(n // md(n), targ) if md(n) else 0)

print(f(150, 7))