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

Ниже подробное решение с пояснениями и примером. Цель: понять алгоритм и увидеть рабочий код на Python.

Что делает задача

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

Какой подход используется

• Проверяем ввод: число должно быть от 1000 до 9999 включительно.
• Перебираем все непустые подпоследовательности цифр в сохранённом порядке. Это удобно сделать через битовые маски для позиции цифр.
• Для каждой подпоследовательности строим само число (по порядку следования цифр в исходном числе).
• Проверяем каждое число на простоту (для чисел до 9999 достаточно простой перебор делителей до sqrt(n)).
• Храним максимум найденного простого числа. В конце выводим максимум (или 0, если простого не было).

Пошаговый разбор на примере 1737

• Все подпоследовательности (упрощённо): 1,7,3,7,17,13,17,73,77,137,177,173,1737 и т.д.
• Среди них простые: 7,17,13,37,73,137,173 и т.д. Наибольший из допустимых — 173.
• Значит для входа 1737 программа выведет 173.

Код на Python

import sys

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

def max_prime_from_digits(num: int) -> int:
    s = str(num)
    n = len(s)
    max_p = 0

    # Проходим по всем непустым подпоследовательностям (маски)
    for mask in range(1, 1 << n):
        val = 0
        for i in range(n):
            if (mask >> i) & 1:
                val = val * 10 + int(s[i])
        if val > 1 and is_prime(val):
            if val > max_p:
                max_p = val

    return max_p

def main():
    data = sys.stdin.read().strip()
    if not data:
        print(0)
        return

    try:
        num = int(data)
    except ValueError:
        print(0)
        return

    # Проверка: должны быть четыре цифры
    if 1000 <= num <= 9999:
        ans = max_prime_from_digits(num)
        print(ans if ans > 0 else 0)
    else:
        print(0)

if __name__ == "__main__":
    main()

Как использовать

• Сохраните код в файл, например, solve.py.
• Запустите: python solve.py
• Введите число, например 1737. Программа выведет 173.

Дополнительные заметки

• Для числа до 9999 перебор подпоследовательностей ограничен 2^4 - 1 = 15 вариантов, поэтому решение очень быстрое.
• Если вход может быть не четверизначным, программа вернёт 0 в соответствии с условием задачи.