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


def f(st, count_operation, set_prime):
    global count
    if count_operation > count:
        return  # выход из программы без действий
    if is_prime(st):
        set_prime.add(st)
    if len(set_prime) == 8:
        count = min(count, count_operation)
        return
    f(st + 3, count_operation + 1, set_prime.copy())
    f(st * 2 - 1, count_operation + 1, set_prime.copy())
    if st > 9:
        f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())


count = 10000000000
f(2, 0, set())
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


primes = [0] * 100000
# для начала определим для каждого числа от 1 до 99999
# простое оно, или нет
for i in range(2, 100000):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0

for operations in range(1000):
    can_get = []
    for i in ans:
        a, pr = i
        if pr == 8:
            otv = operations
            flag = 1
            break
        can_get.append((a + 3, pr + primes[a + 3]))
        can_get.append((a * 2 - 1, pr + primes[a * 2 - 1]))
        if a > 9:
            s = str(a)
            s = s[::-1]
            new_num = int(s) + 1
            can_get.append((new_num, pr + primes[new_num]))
    if flag:
        break
    ans = can_get
                                                                                                     
                                                                                                     
print(otv)