23.08 Прочие прототипы

Решение 1 (Рекурсия)

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

from functools import lru_cache
@lru_cache(None)
def f(st, fn, primes):
    global count
    if is_prime(st):
        primes += 1
    if st == fn:
        if primes < count:
            count = primes
        return
    if st > fn:
        return
    f(st + 1, fn, primes)
    f(st * 2 + 1, fn, primes)
    f(st * 2 - 1, fn, primes)
    f(st * 4 + 1, fn, primes)

count = 100000000000
f(10, 300, 0)
print(count)

Решение 2 (Динамика)

def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1


a, primes = [10000000] * 301, [0] * 301
a[10] = 0
# для начала определим для каждого числа от 1 до 300
# простое оно, или нет
for i in range(2, 301):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
for i in range(10, 300):
    a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
    if i * 2 + 1 < 301:
        a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
    if i * 2 - 1 < 301:
        a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
    if i * 4 + 1 < 301:
        a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])
print(a[300])