На вход подаётся четырёхзначное натуральное число 1737. Написать код на python вывода наибольшее простое число, которое можно составить из цифр введенного числа не переставляя их порядок. Если из цифр невозможно составить натуральное число или введено не четырёхзначное натуральное число, то выводится цифра 0.
Ниже подробное решение с пояснениями и примером. Цель: понять алгоритм и увидеть рабочий код на 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
```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 в соответствии с условием задачи.
