Циклический сдвиг переносит первую цифру числа в конец: 197 превращается в 971, затем в 719. Простое число называется циклическим, если все его сдвиги тоже простые, так что 197 - циклическое простое. Посчитайте циклические простые числа от 2 до limit. Сдвиг может оказаться больше предела, но и тогда он должен быть простым.
Реализуйте circular_primes(limit).
Входные данные
limit: наибольшее число, которое нужно проверить.
Выходные данные
Верните количество циклических простых чисел p ≤ limit.
Ограничения
1 ≤ limit ≤ 100 000
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.