На вход подаётся четырёхзначное натуральное число. Выведите наибольшее простое число, которое можно составить из цифр введенного числа не переставляя их порядок. Если из цифр…

Ниже приведено подробное решение и конкретная реализация на Python.

Цель задачи

• Найти наибольшее простое число, которое можно получить из цифр входного четырехзначного числа, не меняя их порядок (то есть берём любую непустую подпоследовательность цифр и конкатенируем их в исходном порядке).
• Игнорируем варианты с ведущими нулями и недопустимые случаи (если вход не четырехзначное число).
• Если подходящих простых чисел нет, вывести 0.

Пояснение к алгоритму

• Перебираем все непустые подпоследовательности цифр исходного числа. Для четырех цифр это 2^4 - 1 = 15 вариантов.
• Для каждой подпоследовательности исключаем те, что начинаются с 0 (ведь число с ведущим нулём не считается натуральным в обычной записи).
• Преобразуем подпоследовательность в целое число и проверяем на простоту.
• Ведём максимальное найденное простое число. В конце выводим его или 0, если таковых не было.

Псевдокод быстрого обзора

• Если вход не строка из 4 цифр или начинается с 0 — вывести 0.
• max_p = 0
• Для каждого непустого подмножества индексов i из {0,1,2,3}:
  • собрать цифры s[i] в порядке возрастания i
  • если первая цифра равна '0' — пропустить
  • val = int(собранная подпоследовательность)
  • если val — простое и val > max_p — max_p = val
• вывести max_p

Код на Python

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    r = int(n ** 0.5)
    i = 3
    while i <= r:
        if n % i == 0:
            return False
        i += 2
    return True

def main():
    s = input().strip()
    # Проверка: должно быть exactly 4 цифры
    if len(s) != 4 or not s.isdigit():
        print(0)
        return
    # Не допускаем ведущий ноль в исходном числе
    if s[0] == '0':
        print(0)
        return

    max_p = 0
    # Перебираем все непустые подпоследовательности (маски от 1 до 15)
    for mask in range(1, 1 << 4):
        part = []
        for i in range(4):
            if mask & (1 << i):
                part.append(s[i])
        t = ''.join(part)
        # Пропускаем подпоследовательности, начинающиеся с 0
        if t[0] == '0':
            continue
        val = int(t)
        if is_prime(val) and val > max_p:
            max_p = val

    print(max_p)

if __name__ == "__main__":
    main()

Пояснения по примерам

• Для входа 1737 перебор подпоследовательностей даст такие варианты, как 1, 7, 3, 17, 73, 37, 173, 177, 1737 и т.д. Среди них первичные (простые) — 2, 3, 5, 7, 11, 13, 17, 37, 173 и т. д. Наибольшее из допустимых — выводится как требуемое.
• Если вход не четырехзначное число или начинается с 0, сразу выводим 0, как указано в условии.