Проект Эйлера (35 задача). Большая часть проблем задачи решается применением “решета Эратосфена”. Однако есть еще пара улучшений алгоритма.
Узнать больше в телеграм-канале: ProjectEuler++
Число 197 называется круговым простым числом, потому что все перестановки его цифр с конца в начало являются простыми числами: 197, 719 и 971.
Существует тринадцать таких простых чисел меньше 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97.
Сколько существует круговых простых чисел меньше миллиона?
Измеряем время работы программы
Поскольку функция main() получилась объемной, потому чтобы не “мельчить”, решил разбить ее на два скриншота.
Поскольку при решении задачи многократно понадобится проверять числа на то, являются ли они простыми или нет, потому лучше их вычислить заранее.
Для хранения всего ряда чисел (до 1000000) используем массив. Поскольку массив получился объемный, потому при его объявлении используем ключевое слово static (смотрите скриншот выше). Это позволяет хранить его не в стеке, а в основной памяти компьютера.
Хранение чисел по индексу выбрано, потому что это позволяет легко обращаться к ним и определять их статус.
При этом 0 – будет означать простое число, а 1 – составное.
Выбираем 1 для обозначения именно составных чисел, потому что так заполнять массив с помощью “решета Эратосфена” (функцией note_prime_arr()) будет удобней.
Подробнее о работе данной функции – ниже в соответствующих разделах статьи.
После заполнения массива в нем окажется около 80000 простых чисел (от 1 до 1000000), которые гипотетически могут отвечать условиям задачи. Однако и это количество вполне возможно сократить.
Как всем известно, четные числа заведомо не могут быть простыми (потому что они делятся на 2). Таких чисел среди уже вычисленных простых заведомо уже нет (на то они и простые). Однако в процессе круговой перестановки, каждая цифра числа по очереди оказывается в конце. И в итоге, если она четная, то и полученное число будет четным.
Потому каждое простое число перед проверкой раскладывается на цифры, каждая из которых проверяется на четность. При этом, однако, первую цифру можно не проверять и сразу откидывать, потому что первоначальное число – простое.
Таким образом количество проверяемых чисел в итоге сократится многократно (с 80000 до примерно 3000).
Полученное простое число, заведомо не имеющее четных чисел в своем составе, уже проверяем на соответствие условиям задания.
Для начала определяем порядок числа – увеличиваем множитель (fact = 1) до тех про, пока он в итоге не превысит число, уменьшенное на порядок.
Число 197, например, будет иметь множитель:
Получив его, уже не составляет труда перебрать возможные круговые перестановки:
Количество перестановок числа определяется порядком числа и реализовано в цикле for().
Для контроля наличия ответа используем флаг is_answ_fl. В случае если число не удовлетворяет одному из условий, цикл прерывается и флаг принимает значение false.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Первым делом проверяется невыход проверяемого числа за пределы массива. В этом случае работа функции прервется и будет выведено соответствующее предупреждающее сообщение.
Далее функция работает точно так же, как если бы мы определяли простое число. Однако есть отличие.
Поскольку в программе будет использоваться “решето Эратосфена”, потому за единицу удобнее принимать именно составное число.
Отличия от “наивного” алгоритма:
Поскольку многие функции кочуют из одной задачи в другую, потому часто возникают трудно уловимые ошибки. Вроде бы и функция правильная и работает вроде верно, однако контекст задачи изменился и ответ выходит некорректный. Потому, везде где это возможно, делаются проверки ввода.
Для данной проверки и придумана функция input_mote_limit(). Если функция принимает не те значения, на которые она рассчитана, она прекратит ее работу (вернет true – должно дальше обрабатываться) и выведет предупреждение.
Данная функция отмечает составные числа в массиве по принципу “решета Эратосфена”.
Поясню на примере. Начинаем проверять ряд чисел:
В итоге массив выбранной длины заполняется числами на порядки быстрее, чем если бы каждое число проверялось отдельно.
Поскольку ближайшее составное число кратное простому, больше его в два раза, потому отмечать в массиве с него и начнем. Также функция проверяет корректность ввода всех переменных.
Эта функция проходит по массиву от 2 до finish, и найдя простые числа, отмечает кратные им как составные до конца массива. При этом числа уже отмеченные как составные (1) пропускаются.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
