Задача
Число 197 называется круговым простым числом, потому что все перестановки его цифр с конца в начало являются простыми числами: 197, 719 и 971.
Существует тринадцать таких простых чисел меньше 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97.
Сколько существует круговых простых чисел меньше миллиона?
Решение
Простые числа уже много раз фигурировали в предыдущих задачах. Были и простые алгоритмы, и продвинутые, вроде решета Эратосфена.
Так что я не буду ничего усложнять и снова использую простой алгоритм определения простого числа. Нужно просто перебрать множители:
В прошлые разы множители перебирались до значения квадратного корня из n, но и это делать уже лень. Перебор идёт до тех пор, пока множитель не станет больше второго множителя.
Далее нужно перебрать числа до миллиона и выяснить, какие из них простые и круговые. Это поначалу похоже на перестановки из прошлых задач, но всё-таки отличается. Чтобы сделать одну круговую перестановку, нужно взять последнюю цифру числа и перенести в начало. Ну или наоборот.
Вопрос лишь в том, сколько раз это делать. Если в числе 3 цифры, надо переставить 2 раза. Если 4 цифры, то 3 раза, и т.д.
Следовательно, надо определить длину числа. Гуру-питонисты сделали бы так: перевели бы число в строку и получили длину строки. Также можно сделать набор условий: если число меньше 10, то его длина 1, иначе если оно меньше 100, то его длина 2, и т.д. Но это будет не очень хорошо.
Поэтому я разбил общий цикл от 2 до 999999 на диапазоны, где у каждого диапазона своя длина числа:
Это читается как "массив из 6 элементов, где каждый элемент это массив из 2 элементов".
Теперь можно пройти по этому массиву и организовать циклы по значениям его элементов:
Внешний цикл по i считает как элементы массива, так и длину числа, которая на каждом следующем элементе увеличивается на 1. Кроме того, считается множитель mul для переноса последней цифры числа в первую позицию. Например, если число трёхзначное, то mul = 100. Допустим, это число 123. Берём последнюю цифру 3, делим само число на 10, получаем 12. Теперь последнюю цифру умножаем на mul и складываем с 12, получаем 312. Случилась круговая перестановка. И такую перестановку мы повторяем столько раз, сколько цифр в числе (не считая самой первой, которая есть само число).
Нюанс заключается в конструкции while (--len). Операция декремента --, расположенная спереди переменной len, сначала уменьшает её, а потом уже проверяется значение len. Таким образом, если len = 1, то условие сведётся к while (0) и не выполнится.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: