Проект Эйлера (27 задача) решается двумя циклами for() и одной функцией. Однако если уж делать программу, то красиво.
Узнать больше в телеграм-канале: ProjectEuler++
Эйлер опубликовал свою замечательную квадратичную формулу :
- n^2 + n + 41
Оказалось, что согласно данной формуле можно получить 40 простых чисел, последовательно подставляя значения 0≤n≤39Однако, при n = 40,
- 40^2 + 40 + 41 = 40(40 + 1) + 41
делится на 41 без остатка.И, очевидно, при n = 41,
- 41^2 + 41 + 41
делится на 41 без остатка.При помощи компьютеров была найдена невероятная формула
- n^2−79*n + 1601
согласно которой можно получить 80 простых чисел для последовательных значений n от 0 до 79. Произведение коэффициентов −79 и 1601 равно −126479.Рассмотрим квадратичную формулу вида :
- n^2 + a*n + b
где |a| < 1000 и |b| ≤1000, где |n| является модулем(абсолютным значением) n.К примеру, |11|= 11 и |−4| = 4
Найдите произведение коэффициентов a и b квадратичного выражения, согласно которому можно получить максимальное количество простых чисел для последовательных значений n, начиная со значения n = 0
Функции, использующиеся в программе
Решил не мельчить и потому вынес объявление функций и подключение заголовочных файлов на отдельный скриншот.
Если просто следовать заданию, то необходимо:
Изменяя коэффициенты от -1000 до 1000, мы получим 2000 значений a и 2000 значений b и потому четыре миллиона их сочетаний. Однако и значений коэффициента n будут десятки. В итоге формула вернет десятки и сотни миллионов значений, каждые из которых понадобится проверить на то, не являются ли они простыми числами.
Потому “наивный” способ определения простого числа не подойдет (проверить, что оно не делится ни на одно число кроме единицы и самого себя). В итоге эффективней будет вычислить простые числа заранее с помощью “решета Эратосфена” и сохранить в массив.
Однако возникает вторая проблема. Не зная заранее ответ, невозможно точно предсказать до какого числа необходимо вычислять простые числа. Потому в программе будет использоваться динамический массив (переменной длины). По мере необходимости он ступенчато будет увеличиваться и заполняться простыми числами.
Для измерения времени работы программы подключаем библиотеку 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. С него в итоге и начнется заполнение массива.
Также функция проверяет корректность ввода всех переменных.
В отличие от предыдущей эта функция – более сложная. Она не просто отмечает составные числа кратные простому. Она расширяет массив с уже вычисленными простыми и составными числами, новыми числами.
Подразумевается, что в массиве comp_arr[], от индекса 2 до индекса start уже определен статус чисел (простое / составное). Потому на первом этапе функция проходит от 2 до start, и найдя простые числа там, отмечает кратные им в добавляемом диапазоне от start до finish.
На втором этапе собственно уже и проходится добавляемый диапазон. Числа проверяются и найдя простые, отмечаются им кратные.
Данная функция вынесена отдельно, чтобы не загромождать функцию main().
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
