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

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

Посчитайте простые числа до заданного предела, у которых все циклические сдвиги цифр тоже простые.

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

  • Циклически сдвигать цифры числа
  • Проверять условие для каждого сдвига
  • Считать числа, которые проходят проверку

Условие

Циклический сдвиг переносит первую цифру числа в конец: 197 превращается в 971, затем в 719. Простое число называется циклическим, если все его сдвиги тоже простые, так что 197 - циклическое простое. Посчитайте циклические простые числа от 2 до limit. Сдвиг может оказаться больше предела, но и тогда он должен быть простым.

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

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

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

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

Верните количество циклических простых чисел p ≤ limit.

Ограничения

1 ≤ limit ≤ 100 000

Примеры

Пример 1
Ввод:
limit = 20

Ожидаемый вывод:
expected = 7
Ввод:
long long limit = 20;

Ожидаемый вывод:
long long expected = 7;
Ввод:
long limit = 20;

Ожидаемый вывод:
long expected = 7;

Пояснение

2, 3, 5, 7, 11, 13 (31 простое) и 17 (71 простое) циклические, а 19 нет (91 = 7 × 13): 7.

Пример 2
Ввод:
limit = 1

Ожидаемый вывод:
expected = 0
Ввод:
long long limit = 1;

Ожидаемый вывод:
long long expected = 0;
Ввод:
long limit = 1;

Ожидаемый вывод:
long expected = 0;

Пояснение

До 1 простых чисел нет, поэтому ответ 0.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Один сдвиг переносит первую цифру в конец; у d-значного числа d сдвигов.

Подсказка 2

Если превратить число в строку, сдвигать его будет просто.

Подсказка 3

Сдвиги могут быть больше предела, поэтому проверяйте их на простоту напрямую.

Ожидаемая сложность

время O(limit × d × √(10^d)) при переборе делителей, доп. память O(d)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

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

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

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

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

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