Программа C++ для печати максимально возможного простого числа из заданного числа
Опубликовано: 9 Января, 2023
Для заданного целого числа задача состоит в том, чтобы найти наибольшее простое число, которое можно из него составить. Если рассматривать целое число как строку цифр, то простое число может быть подстрокой любой длины. Приведенные ниже примеры пояснят суть задачи.
Пример:
Input: 12691
Output: 691
Explanation: The three numbers in the number 12691 are 269,691. The greater number is 691 and hence we print this.
Подход:
- Создать строку заданного числа
- Вычислить все подстроки строки
- Проверить, является ли какая-либо подстрока простой или нет
- Если подстрока является простой, максимизируйте ее значение, сравнивая ее с другими простыми подстроками.
- Возвращает максимальное значение основной подстроки
Временная сложность: O(N 3 )
Вспомогательное пространство: O(1)