Проект Эйлера (10 задача) из тех, которые наивным перебором уже не решаются. Данный вариант решения – через “решето Эратосфена”
Узнать больше в телеграм-канале: ProjectEuler++
Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17.
Найдите сумму всех простых чисел меньше двух миллионов.
Это первое, что приходит в голову, глядя на условия задачи. Однако при этом каждое число необходимо проверить, не является ли оно простым. В итоге нам потребуется сделать два миллиона проверок.
При этом основной проблемой будет проверка, являются ли числа простыми. Потому что, согласно определению, число является простым, если делится только на единицу и на само себя.
Чтобы проверить, является ли число 5 простым, в итоге понадобятся следующие операции:
Убедившись, что ни одно число не делит 5 нацело, в итоге можно сделать вывод, что оно простое.
Конечно, в программе эти операции будут выглядеть в виде одной строчки кода. Однако это не отменяет того, что для проверки числа 2000000 понадобится два миллиона операций деления. А для числа перед ним – 1999999 еще почти два миллиона операций.
Т.е. использование простого алгоритма в итоге приведет к миллиардам операций.
В этом варианте решения делаем все наоборот. Находим не простые числа, а составные.
Возьмем, к примеру, ряд чисел до 10. Вместо того, чтобы проверять каждое число (делением), действуем следующим образом:
И в итоге, для ряда чисел до 1000000, к примеру, уже на первой итерации (с 2) 500000 откинутся, потому что они делятся на 2. Потому их не нужно будет проверять классическим способом.
Для хранения статуса чисел создаем массив и заполняем его нулями.
Нули, в данном случае будут указывать, что статус числа или не определен или число простое: массив[число] = 0.
При этом статус числа 1 в данном случае будет означать составное число: массив[число] = 1.
Ключевое слово static указывает, что локальная переменная является статической. Она расположена не в стековом фрейме (с ограниченным объемом памяти), а в основной памяти устройства. В данном случае это необходимо для размещения довольно таки большого массива.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
Любое значение num, отличное от нуля, будет восприниматься как true и код после if будет выполняться
! инвертирует значение num: true в false и наоборот
Логическое “И” возвращает true только, если true && true
Тоже самое, что и answ = answ + num
Для начала напомню понятия.
Потому в ряду натуральных чисел 2, 3, 4, 5... все числа либо простые, либо составные.
Алгоритм определения составного числа, в итоге, как бы обратный алгоритму определения простого. Потому, чтобы определить, что число составное, нужно найти хотя бы один делитель в диапазоне большем единицы и меньше проверяемого числа.
Во-первых, нет необходимости делить на все числа от единицы до самого числа при проверке.
Например, возьмем небольшое число (12) и будем раскладывать его на множители:
Ясно видно, что первое и второе множества повторяют третье и четвертое. Потому что только множители меняются местами.
Чтобы определить является ли число (12) составным, в итоге можно не делить его на весь ряд чисел: 2, 3, 4… 10, 11. Потому что достаточно проверить до корня квадратного из числа (sqrt(12) = 3.464). В данном случае это числа 2, 3, 4. Если делители до этого момента не найдены, дальше можно не искать – потому что число простое.
Так, например, для числа 1000000, в итоге, достаточно будет проверять делимость только до 1000 (а не до 1000000). Ощутимая оптимизация!
Во-вторых, функцию sqrt() – вычисления квадратного корня из числа, необходимо вынести из цикла for(). Это необходимо потому, что некоторые компиляторы могут решить вычислять ее на каждой итерации. Даже в языке Си эта функция довольно таки трудозатратна, что уж говорить про другие.
В-третьих, проверять делимость следует только простыми числами.
К примеру, если число не делится на 2, то нет в итоге смысла проверять делимость и на 4. Делаем так потому, что если число делится на 4, то оно автоматически делится и на 2.
Для хранения составных чисел создается массив, в котором индекс – это значение числа. При этом, напомню, что в массиве сохраняются только два значения: 1 – составное число, 0 – простое.
Каждое вычисленное простое число в итоге заносится в массив, который в дальнейшем используется самой функцией.
Подключаем стандартную библиотеку языка Си для работы с булевым типом данных.
Для стандарта C99 булевый тип _Bool, который принимает значения 0 и 1. Данная библиотека позволяет использовать более привычный тип данных bool со значениями false и true.
Подключаем стандартную математическую библиотеку языка Си. Необходима для работы функции sqrt()
Директива макропроцессора #define заменяет в тексте программы строку LEN_ARR на цифры 2000000 перед компиляцией
Данная функция (is_composite()) описана выше. Определяет не только составные числа (как true), но и простые (возвращает false).
После чего функция note_composite() принимает, определенное таким образом, простое число (step) и отмечает в массиве все числа, делимые на него как составные. Просто отмечается числа следующее за start с шагом step.
Единственный интересный момент здесь в определении первого числа, с которого функция начнет отмечать. Потому что, если простое число это 2, а отмечать нужно с 1000, то никаких проблем нет. Отмечаем числа 1000, 1002, 1004 и так далее. Однако если простое число 3, то нельзя начинать отмечать с 1000, потому что 1000 не делится нацело на 3. Потому вычисляется смещение (shift), с помощью которого получается первое число – в конкретном случае 1002. В итоге отмечаются числа 1002, 1005, 1008 и так далее.
Кроме того в процессе работы функция подсчитывает количество отмеченных в массиве составных чисел и в итоге это число возвращает.
Используем тернарный оператор. Выражение можно преобразовать следующим образом:
Ответ на 10 задачу проекта Эйлера в итоге составил 142913828922, программа работает довольно быстро – примерно 270 миллисекунд.
При прочих равных запускал этот же код без использования “решета Эратосфена” – работал примерно на 0.1 секунды дольше. Думаю, при больших объемах вычислений разница будет больше.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
