Возьмём 3797. Если удалять цифры слева, получим 797, 97 и 7, а если справа, то 379, 37 и 3. Все эти числа простые, как и само 3797. Назовём такое простое число усекаемым с обеих сторон. Однозначным простым числам нечего удалять, и они не считаются. Выведите все усекаемые с обеих сторон простые числа от 10 до limit.
Реализуйте truncatable_primes(limit).
Входные данные
limit: наибольшее число, которое нужно проверить.
Выходные данные
Верните эти простые числа в порядке возрастания. Если их нет, верните пустой список.
Ограничения
1 ≤ limit ≤ 100 000
Примеры
Ввод:
limit = 40
Ожидаемый вывод:
expected = [23, 37]
Ввод:
long long limit = 40;
Ожидаемый вывод:
std::vector<long long> expected = {23, 37};
Ввод:
long limit = 40;
Ожидаемый вывод:
long[] expected = new long[] {23, 37};
Пояснение
23 (2, 3) и 37 (3, 7) подходят; 13 не подходит, потому что 1 не простое, а 29 не подходит, потому что 9 не простое. [23, 37].
Ввод:
limit = 10
Ожидаемый вывод:
expected = []
Ввод:
long long limit = 10;
Ожидаемый вывод:
std::vector<long long> expected = {};
Ввод:
long limit = 10;
Ожидаемый вывод:
long[] expected = new long[] {};
Пояснение
Меньше 10 есть только однозначные простые числа, а они не считаются: [].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Удаление цифры справа - это деление на 10.
Подсказка 2
Удаление цифр слева - это взятие остатка по модулю степени 10.
Подсказка 3
Простыми должны быть все усечения вплоть до одной цифры, а также само число.
Ожидаемая сложность
время O(limit × d × √limit), доп. память O(answer)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.