Проект Эйлера (46 задача). Даже в такой простой задаче возможно реализовать динамический массив, “хеширование” данных и битовые операции.
Узнать больше в телеграм-канале: ProjectEuler++
Кристиан Гольдбах показал, что любое нечетное составное число можно записать в виде суммы простого числа и удвоенного квадрата.
- 9 = 7 + 2×12
- 15 = 7 + 2×22
- 21 = 3 + 2×32
- 25 = 7 + 2×32
- 27 = 19 + 2×22
- 33 = 31 + 2×12
Оказалось, что данная гипотеза неверна.
Каково наименьшее нечетное составное число, которое нельзя записать в виде суммы простого числа и удвоенного квадрата?
Измеряем время работы программы
Функции, используемые в программе
В данном случае решил не загромождать код и разделить его на три файла:
Чтобы определить ответ, будем перебирать нечетные числа (+=2) от меньшего к большему. Те из них, что не являются простыми, будем проверять на удовлетворение условиям Гольдбаха, следующим образом:
Если для проверяемого числа мы перебрали все удвоенные квадраты чисел до него самого (для 9 это 2 * (2^2) = 8) и ни одна полученная разность не была бы простым числом, то проверяемое число не удовлетворяет условиям Гольдбаха. Поскольку перебор проверяемых чисел мы ведем от меньшего к большему, потому найденное число будет искомым ответом.
Поскольку в процессе вычисления нам понадобится многократно определять простые ли числа, потому вычисленные простые числа будем сохранять структуре struct list. Структура содержит ссылку на массив и его длину. Т.к. как заранее неизвестна необходимая длина массива, потому память для него будем выделять динамически с помощью calloc().
Числа в массиве будут храниться по их индексу, однако чтобы уменьшить длину массива на порядок, в ячейке будет храниться не одно значение, а несколько.
Т.е. в массиве будет храниться не два возможных значения (1 / 0 : простое / составное число):
… а больше.
Простые числа в нашем случае будут храниться в массиве в виде включенных / выключенных битов:
Для внесения отдельных битов в ячейку как раз и используем перечисление enum bit_nums.
Если в ячейке включено несколько битов, например:
…значит, в ячейку занесены два числа:
Перечисление сделано для передачи аргумента в функцию check().
При передаче more функция будет срабатывать при превышении аргументом заданного лимита, а less – при уменьшении.
Также выносим в этот файл объявления функций, использующихся в функции main().
К каждой из них пишем комментарий по ее использованию посторонним пользователем (возможно это будете именно Вы же, но через полгода). В качестве аргументов функции будут принимать указатели на структуры вне зависимости от того, изменяет ли функция ее содержание. Это сделано для того, чтобы пользователь не путался, где нужно использовать указатели, а где нет. Там, где данные в структуре изменяться не будут, просто пишем const.
Разбил main() на два скриншота, чтобы не мельчить.
При начале работы пользователю предлагается ввести, до какого числа искать ответ. Это нужно для того, чтобы выделить соответствующее количество памяти для структуры с простыми числами и массива удвоенных квадратов чисел.
Поскольку для проверки условий Гольдбаха достаточно знать ряд простых чисел и удвоенных квадратов натуральных чисел до проверяемого числа включительно, потому вычислять простые числа и удвоенные квадраты будем не сразу все, а постепенно.
Далее, если число не является простым, оно проверяется на удовлетворение условиям Гольдбаха, как уже описано в алгоритме.
Первое найденное число не удовлетворяющее этим условиям будет искомым ответом.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Все функции, используемые в программе вынес в файл “funcs.c“. Их работа довольно подробно описана в комментариях к коду, но повторюсь.
Данная функция в случае выхода контролируемого параметра за назначенные пределы (его превышения или уменьшения) выводит информационное сообщение об этом и возвращает true для дальнейшей обработки ошибки.
Данная функция является служебной и служит частью реализации программы, но не его интерфейса и потому скрыта от использования из других файлов ключевым словом const.
Также в целях ускорения используем ключевое слово inline, указывая, что функция является встраиваемой.
Выделяет память нужного размера для структуры struct list, заполняет все поля нулями и возвращает ее.
В случае неуспешного выделения памяти, поле структуры *arr будет указывать не на массив, а на NULL.
Служит для внесения простого числа в массив.
Для хранения простых чисел используем массив на порядок меньший хранимому числу. Т.е. для хранения числа 12345 нам не нужен char-массив длиной 12345, а вполне достаточно 1234 байта.
Так происходит потому, что последний разряд числа зашифрован в виде отдельных битов:
Четные цифры не шифруем, потому что четные числа заведомо не могут быть простыми.
Такой способ хранения позволяет в одной ячейке хранить несколько цифр, например:
…и для ячейки:
Биты в ячейку заносятся с помощью битового ИЛИ:
Данная функция возвращает является ли число простым, просто проверяя его наличие в заранее заполненном массиве простых чисел с помощью операции побитового И.
Напоминаю, что простое число делится только на единицу и само на себя. Данная функция перебирает нечетные числа, следующие за последним простым числом, проверяет их и возвращает первое же найденное простое число.
Особенности:
Если по окончании перебора делитель не найден, то число является простым.
Иначе таким же образом проверяется следующее нечетное число.
Если проверяемое число превысило длину массива, то работа функции останавливается и возвращается false (0).
Данная функция проверяет соответствие числа условиям Гольдбаха.
Т.е. перебирает удвоенные квадраты натуральных чисел от меньшего к большему пока не превысит проверяемое число или пока разность числа и удвоенного квадрата текущего числа не окажется простым числом.
Функция вернет false только в том случае, если в этом диапазоне среди разностей проверяемого числа и удвоенных квадратов простых чисел не было.
В зависимости от того, найден ли на заданном диапазоне ответ, вывод будет разный.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
