Найдите как можно большее натуральное число с попарно различными цифрами, обладающее следующим свойством: любое двузначное число, образованное двумя соседними
цифрами в порядке их следования в числе, является простым. (Например, таким свойством обладает число 473, поскольку 47 и 73 — простые числа.)

Требование "с попарно различными цифрами" означает, что число может быть не более чем десятизначным. На деле же - не более чем девятизначным, потому что 0 не присутствует не в одном простом числе.
Но есть и ещё одно довольно сильное ограничение: в этом числе не могут присутствовать чётные цифры. Потому что при выделении пар соседних чисел неизбежно будут присутствовать оканчивающиеся на чётную, а такие числа простыми не являются.
Ну и пятёрка. Цифра 5 тоже не может присутствовать, потому как любое двузначное число, оканчивающееся на 5, не будет простым.
Однако как пятёрка, так и чётная цифра могут быть самой первой цифрой нашего числа.
Так что число может быть только четырёхзначным и составленным из цифр 1, 3, 7, 9, либо пятизначным и начинающимся с пятёрки или чётной цифры. И вполне понятно, что любое пятизначное больше любого четырёхзначного.
Начнём с пятёрки.
Чисто интуитивно представляется логичным иметь максимально возможную цифру после начальной пятёрки. По счастью, число 59 - простое, так что начать наше девятизначное число с 59.
Требование того, что простые числа тут двузначные, ограничивает выбор простых чисел диапазоном от 13 (11 не годится - не выполняется требования попарной различности)
Простых чисел, которые начинаются с 9, всего одно: 97. Это даёт нам три первых цифры искомого числа - 597.
Простых чисел, начинающихся на 7, три: 71, 73, 79. Девятка уже пристроена, так что берём следующее максимально возможное. В итоге имеем ещё одну цифру, и число начинается с 5973.
Ну и для последней цифры остаётся только единица. Тут опять пруха, потому что 31 - тоже простое число.
Окончательный ответ - 59731.
Теперь посмотрим, что будет, если число начинается с чётной цифры. Максимальный вариант - 8. Простые числа, начинающиеся с 8, - это 83 и 89. Ура, 89 тоже подходит! Значит, дальше можно рассуждать ровно так же, как и давеча, поэтому вариант для первый восьмёрки - 89731.
Ну вот это и будет совсем окончательный ответ в задачке.