Проект Эйлера (7 задача) не решается с наскоку. Привел два варианта решения задачи: продвинутый классический и с помощью “решета Эратосфена”
Узнать больше в телеграм-канале: ProjectEuler++
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число – 13.
Какое число является 10001-м простым числом?
Первое, что приходит в голову, глядя на условия задачи – это последовательный перебор чисел. При этом каждое число необходимо проверить, не является ли оно простым. В итоге, все найденные простые числа необходимо считать до тех пор, пока не дойдем до искомого номера (10001).
Потому, этот вариант и назван мной “классическим“.
При этом основной проблемой будет проверка, являются ли числа простыми. Потому что, согласно определению, число является простым, если делится только на единицу и на само себя.
В итоге, чтобы проверить, является ли число 5 простым, нужны следующие операции:
Убедившись, что ни одно число не делит 5 нацело, можно сделать вывод, что оно простое.
Конечно, в программе эти операции будут выглядеть в виде одной строчки кода. Однако это не отменяет того, что для проверки числа 1000000 понадобится миллион операций деления. А для числа перед ним – 999999 еще почти миллион операций.
В итоге использование простого алгоритма приводит к миллиардам операций.
Во-первых, нет необходимости делить на все числа от единицы до самого числа при проверке.
Например, возьмем небольшое число (12) и будем раскладывать его на множители:
Ясно видно, что первое и второе множества повторяют третье и четвертое. Только множители меняются местами.
Потому, чтобы определить является ли число (12) простым, можно не делить его на весь ряд чисел: 2, 3, 4… 10, 11. Потому что достаточно проверить до корня квадратного из числа (sqrt(12) = 3.464). В данном случае это числа 2, 3, 4.
В итоге, для 1000000 (к примеру) достаточно будет проверять делимость только до 1000 (а не до 1000000). Уже ощутимая оптимизация!
Во-вторых, функцию sqrt() – вычисления квадратного корня из числа необходимо вынести из цикла for() (смотрите фото выше). Это необходимо потому, что некоторые компиляторы могут решить вычислять ее на каждой итерации. Даже в языке Си эта функция довольно таки трудозатратна, что уж говорить про другие.
В-третьих, проверять делимость следует только простыми числами.
К примеру, если число не делится на 2, то нет смысла проверять делимость на 4. Делаем так потому, что если число делится на 4, то оно автоматически делится и на 2.
Реализовано это следующим образом:
Подключаем стандартную библиотеку языка Си для работы с булевым типом данных.
Для стандарта C99 булевый тип _Bool, который принимает значения 0 и 1. Данная библиотека позволяет использовать более привычный тип данных bool со значениями false и true.
Подключаем стандартную математическую библиотеку языка Си. Необходима для работы функции sqrt()
Директива макропроцессора #define заменяет в тексте программы строку LEN_ARR на цифры 200000 перед компиляцией
Как уже описано выше, для хранения чисел создаем массив:
Явно указываем, что число 2 – простое, чтобы функция is_simple() не пропустила его при заполнении массива.
Далее в цикле while() перебираются числа и по порядку проверяются. Каждое простое число подсчитывается. В итоге цикл прерывается при достижении искомого счета (10001).
Ключевое слово static указывает, что локальная переменная является статической. Она расположена не в стековом фрейме (с ограниченным объемом памяти), а в основной памяти устройства. В данном случае это необходимо для размещения довольно таки большого массива.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
В этом варианте решения делаем все наоборот. Находим не простые числа, а составные.
Возьмем, к примеру, ряд чисел до 10. Вместо того, чтобы проверять каждое число (делением), действуем следующим образом:
В итоге, для ряда чисел до 1000000, к примеру, уже на первой итерации (с 2) 500000 откинутся, потому что они делятся на 2. Их не нужно будет проверять классическим способом.
Так же как и в классическом варианте решения, создаем массив для хранения статуса чисел. Однако статус числа 1 в данном случае означает не простое, а составное число:
С помощью функции is_composite() определяется статус чисел в массиве до 1000.
При этом счетчиком cnt_comp подсчитываются составные числа. Поскольку между от числа 2 до 1000 находится 998 чисел, потому количество простых чисел в этом диапазоне определяется как разность 998 – cnt_comp.
Работает функция точно также как и функция для определения простого числа. Однако есть отличия:
Подключаем стандартную библиотеку языка Си для работы с булевым типом данных.
Для стандарта C99 булевый тип _Bool, который принимает значения 0 и 1. Данная библиотека позволяет использовать более привычный тип данных bool со значениями false и true.
Подключаем стандартную математическую библиотеку языка Си. Необходима для работы функции sqrt()
Директива макропроцессора #define заменяет в тексте программы строку LEN_ARR на цифры 200000 перед компиляцией
Функция note_composite() уже работает на выше описанном алгоритме “решета Эратосфена”.
Далее цикл повторяется, пока не превзойдет искомую цифру количества простых чисел (10001). На основе чисел с уже определенным статусом отмечаются числа между 2000 и 3000, 3000 и 4000 и т.д.
Функция принимает простое число (step) и отмечает в массиве, все числа, делимые на него как составные. Просто отмечается первое число (start), потом следующее (start + step) с шагом step.
Единственный интересный момент здесь в определении первого числа, с которого функция начнет отмечать. Потому что, если простое число это 2, а отмечать нужно с 1000, то никаких проблем нет. Отмечаем числа 1000, 1002, 1004 и так далее. Однако если простое число 3, то нельзя начинать отмечать с 1000, потому что 1000 не делится нацело на 3. Потому вычисляется смещение (shift), с помощью которого получается первое число – в конкретном случае 1002. В итоге отмечаются числа 1002, 1005, 1008 и так далее.
В процессе работы функция подсчитывает количество отмеченных в массиве составных чисел и в итоге это количество возвращает.
Используем тернарный оператор. Выражение можно преобразовать следующим образом:
В процессе поиска диапазона, в котором находится искомое простое число, ряд чисел с определенным статусом увеличивается на 1000 с каждой итерацией. На каждой итерации обновляется счетчик уже определенных простых чисел cnt_prime. Однако при этом его предыдущее состояние (до итерации) сохраняется в другой счетчик past_cnt_prime.
В итоге на последней итерации мы получим (условно) следующие данные.
Тут все просто. На заданном отрезке массива функция считает простые числа и в итоге возвращает значение с искомым номером.
В итоге ответ на 7 задачу проекта Эйлера составил 104743, программа работает довольно быстро 7 – 8 миллисекунд. Классический вариант программы считает примерно так же.
Пока прибавка скорости значительная только относительно наивного алгоритма поиска простых чисел – простым перебором. В последующих, более сложных задачах проекта Эйлера разница между продвинутым классическим вариантом и алгоритмом через решето Эратосфена будет более заметна.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
