Все задачи
Средне Решено: 0 Процент решений: 0%

Усекаемые простые числа

Выведите простые числа до заданного предела, которые остаются простыми при удалении цифр с любого конца.

Чему вы научитесь

  • Удалять цифры с любого конца числа
  • Проверять каждое усечение
  • Собирать результаты по порядку

Условие

Возьмём 3797. Если удалять цифры слева, получим 797, 97 и 7, а если справа, то 379, 37 и 3. Все эти числа простые, как и само 3797. Назовём такое простое число усекаемым с обеих сторон. Однозначным простым числам нечего удалять, и они не считаются. Выведите все усекаемые с обеих сторон простые числа от 10 до limit.

Реализуйте truncatable_primes(limit).

Входные данные

limit: наибольшее число, которое нужно проверить.

Выходные данные

Верните эти простые числа в порядке возрастания. Если их нет, верните пустой список.

Ограничения

1 ≤ limit ≤ 100 000

Примеры

Пример 1
Ввод:
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].

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.