Проект Эйлера (37 задача). Для ускорения программы определим ряд простых чисел при помощи решета Эратосфена и сохраним в динамический массив.
Узнать больше в телеграм-канале: ProjectEuler++
Число 3797 обладает интересным свойством. Будучи само по себе простым числом, из него можно последовательно выбрасывать цифры слева направо, число же при этом остается простым на каждом этапе: 3797, 797, 97, 7. Точно таким же способом можно выбрасывать цифры справа налево: 3797, 379, 37, 3.
Найдите сумму единственных одиннадцати простых чисел, из которых можно выбрасывать цифры как справа налево, так и слева направо, но числа при этом остаются простыми.
ПРИМЕЧАНИЕ: числа 2, 3, 5 и 7 таковыми не считаются.
Измеряем время работы программы
Функции, использующиеся в программе
Поскольку функция main() получилась объемной, потому чтобы не “мельчить”, решил разбить ее на два скриншота.
Создаем массив (смотрите скриншот выше) для хранения простых и составных чисел длиной 100000 (для начала) и заполняем его нулями с помощью функции calloc().
Далее с помощью функции note_prime_arr(), описанной ниже, заполним массив значениями простых и составных чисел.
Числа (num) будут перебираться и простые из них будут проверяться на соответствие условиям задачи с помощью функций del_right_num() и del_left_num() также описанных ниже.
Полученные ответы суммируются. В случае если длины массива уже не достаточно, его длина увеличивается с тем же шагом 100000.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Сначала с помощью функции calloc() запрашивается место под новый (увеличенный) массив в памяти. В случае, если что-то пошло не так, функция выведет предупреждение, прервет свою работу и вернет указатель на старый массив.
Однако, если все удачно, участок памяти заполняется нулями и calloc() возвращает указатель на выделенный участок.
Далее, со старого массива информация переносится на новый и старый массив удаляется. Изменяется и значение переменной len_arr, хранящей длину массива.
Возвращать в итоге функция будет указатель уже на новый массив.
Напомню, что составное число – это число не являющееся простым. Т.е. то, которое делится на какое-либо число, кроме единицы и себя самого.
Числа в массиве будут сохраняться по индексу следующим образом:
Хранение чисел по индексу выбрано, потому что это позволяет легко обращаться к ним и определять их статус.
Первым делом проверяется невыход проверяемого числа за пределы массива. В этом случае работа функции прервется и будет выведено соответствующее предупреждающее сообщение.
Далее функция работает точно так же, как если бы мы определяли простое число. Однако есть отличие.
Поскольку в программе будет использоваться “решето Эратосфена”, потому за единицу удобнее принимать именно составное число.
Отличия от “наивного” алгоритма:
Поскольку многие функции кочуют из одной задачи в другую, потому часто возникают трудно уловимые ошибки. Вроде бы и функция правильная и работает вроде верно, однако контекст задачи изменился и ответ выходит некорректный. Потому, везде где это возможно, делаются проверки ввода.
Для данной проверки и придумана функция input_mote_limit(). Если функция принимает не те значения, на которые она рассчитана, она прекратит ее работу (вернет true – должно дальше обрабатываться) и выведет предупреждение.
Данная функция отмечает составные числа в массиве по принципу “решета Эратосфена”.
Поясню на примере. Начинаем проверять ряд чисел:
В итоге массив выбранной длины заполняется числами на порядки быстрее, чем если бы каждое число проверялось отдельно.
Поскольку функция позволяет заполнять массивы с любого выбранного числа, потому первое отмеченное число вычисляется.
Например, простое число (prime) задается как 3 и начало заполнения массива определено с 13 (start). В этом случае первым составным числом, кратным 3, будет 15. С него в итоге и начнется заполнение массива.
Также функция проверяет корректность ввода всех переменных.
В отличие от предыдущей эта функция – более сложная. Она не просто отмечает составные числа кратные простому. Она расширяет массив с уже вычисленными простыми и составными числами, новыми числами.
Поскольку при создании массив изначально заполнен нулями, присвоим ячейкам с индексами 0 и 1 в массиве статус 1 (число не являющееся простым).
Подразумевается, что в массиве comp_arr[], от индекса 2 до индекса start может быть уже определен статус чисел (простое / составное). Потому на первом этапе функция проходит от 2 до start, и найдя простые числа там, отмечает кратные им в добавляемом диапазоне от start до finish.
На втором этапе собственно уже и проходится добавляемый диапазон. Числа проверяются и найдя простые, отмечаются им кратные.
Как и требовалось в задании, данная функция отрезает от числа цифры справа по одной и проверяет на то, простые ли они. Как только одно из укороченных чисел окажется составным, функция прервется и вернет false.
Данная функция отрезает от числа цифры теперь слева по одной и проверяет на то, простые ли они.
На первом этапе определяется порядок числа. Делитель (div) увеличивается до тех пор, пока не достигнет нужного порядка:
Далее с помощью делителя отделяется старшая цифра (слева) и получается укороченное число:
По мере уменьшения числа, уменьшается и порядок делителя. Каждое укороченное число проверяется в массиве. Как только одно из них окажется составным, функция прервется и вернет false.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
