На вход подаётся четырёхзначное натуральное число. Выведите наибольшее простое число, которое можно составить из цифр введенного числа не переставляя их порядок. Если из цифр невозможно составить натуральное число или введено не четырёхзначное натуральное число, то выводится цифра 0. Например, из числа 1737 можно выделить несколько простых чисел 1737-17,1737-7,1737-3, 1737-73, 1737-37, 1737-173, Программа не должна выводить цичего кроме требуемого.привести конкретную реализацию на языке Python
Ниже приведено подробное решение и конкретная реализация на 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
```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, как указано в условии.
