Сразу воспользовался алгоритмом определения простого числа, разработанного для задачи Эйлера #3, постарался ускорить программу с помощью использования указателей, и лишь затем воспользовался "наивным" алгоритмом, чтобы убедиться в его бесперспективности.
Условия задачи
"Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17.
Найдите сумму всех простых чисел меньше двух миллионов."
Первый вариант программы
Описание "наивного" алгоритма
Ну прежде всего напомню, что простые числа по определению делятся только на единицу и сами на себя.
Таким образом, "наивный" алгоритм проверки на то, является ли число простым, подразумевал бы деление числа на весь ряд чисел от единицы до него самого.
Не страшно, если это небольшое число. Так 11 нужно последовательно разделить на числа 2, 3 ... 9, 10. Проблемы будут для больших чисел вида 123455678.
Бесперспективность "наивного" алгоритма продемонстрирую в конце статьи.
Описание "продвинутой" функции, для определения простого числа
Как писал я ранее, чтобы удостовериться что число (A = a*a) не делится нацело ни на одно число из ряда от 1 до A, достаточно проверить, что оно не делится ни на одно число из ряда от 1 до a (корня квадратного из A).
На этой идее работает функция is_simple().
Также хотел отметить, что функция sqrt(), вычисляя корень из числа, возвращает дробное число, но при присвоении переменной i_arg дробная часть будет отброшена, т.к. она имеет тип int. Использование целочисленных данных необходимо для работы цикла for в дальнейшем.
Описание работы самой программы
Под влиянием более опытных товарищей решил отнестись к задаче максимально серьезно... и начал "гуглить")))
Увы, волшебной формулы, что быстро вычисляет ряд простых чисел не нашел(.
По итогу в программе просто перебираются все числа до 2000000, проверяются и простые суммируются. Ничего лучшего не придумал.
Результаты работы программы
Время работы программы: 0.8 - 0.9 секунды, что неплохо.
Второй вариант программы
Вместо того, чтобы копировать данные из одной функции в другую, воспользовался указателями и передавал только адреса переменных в памяти. Подробнее об этом здесь.
Пояснения по используемым в программе библиотекам также описывал ранее.
Ответ на задачу:
Запустил несколько раз и видно, что скорость вычислений незначительно выросла. Хотя может быть это самовнушение)
Бесперспективность "наивного" алгоритма
В этой программе, для определения простого числа, проверяются все числа вплоть до него самого.
Включил, подождал, сходил попил чайку)) остановил программу. Очевидно, что будет долго.
Попробовав разные числа, понял, что за адекватное время вычисляется сумма простых чисел до 1000000.
До 1000000 считает сумму простых чисел за 60 секунд, что наглядно показывает достоинства "продвинутого" варианта.
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера #10 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))