Найдите простое число S, содержащее в себе данное число N.

Для заданного целого числа N найдите простое число S такое, что все цифры числа N встречаются в непрерывной последовательности. Может быть несколько ответов. Распечатайте любой из них.

Пример:

Input: N = 42
Output: 42013
Explanation: 42013 is a prime and 42 occurs as a contiguous number in it. 15427 is also a correct answer.

Input: N = 47
Output: 47
Explanation: 47 itself is a prime

Наивный подход: можно выполнить следующие шаги:

• Перебрать все числа, начиная с N
• Преобразуйте каждое число в строку с помощью функции to_string()
• Проверить наличие необходимой подстроки с помощью функции str.find()
• Если есть какое-либо число, которое имеет N в качестве подстроки и является простым, верните это число

Временная сложность: O(S), где S — требуемое простое число.

Эффективный подход: можно выполнить следующие шаги:

• Можно использовать тот факт, что число со значением до 1e12 между двумя последовательными простыми числами находится не более 464 не простых чисел.
• Расширьте текущее число N , умножив его на 1000.
• После этого перебирайте следующие числа одно за другим и проверяйте каждое из них.
• Если число простое, то выведите это число.
• Легко видеть, что первое условие всегда будет следовать за цифрами, за исключением того, что последние три будут N.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(sqrt(N*1000)*300)
Вспомогательное пространство: O(1)