Пожалуй, основной оптимизацией в данной задаче является вычисление списка простых чисел с помощью «решета Эратосфена»
Условия задачи
Простое число 41 можно записать в виде суммы шести последовательных простых чисел:
41 = 2 + 3 + 5 + 7 + 11 + 13
Это - самая длинная сумма последовательных простых чисел, в результате которой получается простое число меньше одной сотни.
Самая длинная сумма последовательных простых чисел, в результате которой получается простое число меньше одной тысячи, содержит 21 слагаемое и равна 953.
Какое из простых чисел меньше одного миллиона можно записать в виде суммы наибольшего количества последовательных простых чисел?
Описание работы программы
Поскольку нам многократно понадобятся значения простых чисел до миллиона, то вычислим их заранее и сохраним в массив по индексу.
- массив[число] = 0; // простое число
- массив[число] = 1; // составное
При этом эффективней это сделать, отметив составные числа в массиве с помощью «решета Эратосфена»
Функция для определения составного числа
Тема обсуждается не первый раз, но кратко напишу для случайного читателя.
Функция is_conposite() перебирает в цикле делители числа. Если находится делитель отличный от единицы и самого проверяемого числа, то число является не простым, а составным.
Основные хитрости алгоритма:
- Делители проверяются только до корня квадратного из проверяемого числа, если к тому времени делитель не найден - число простое.
- Функция вычисления квадратного корня - sqrt() вычисляется довольно долго. Выносим ее перед циклом for(), чтобы избежать вычисления на каждой итерации.
- Функция принимает указатель на массив с уже вычисленными составными числами и проверяет в качестве делителей только простые числа. Это делаем потому, что составные числа сами являются делимыми на простые.
Функция, отмечающая составные числа в массиве
Функция note_composite() использует «решето Эратосфена» в своей работе. А именно:
- Принимает простое число - 2.
- Отмечает числа кратные 2 как составные: 4, 6, 8…
- 3 -> отмечает 6, 9, 12…
- И так далее.
Алгоритм решения
Имея список вычисленных простых чисел (значение 0 в массиве), начинаем составлять цепочки из них. При этом считается длина цепочки и проверяется не является ли сумма простым числом.
Значение максимальной длины цепочки и соответствующего ей простого числа (равное сумме простых чисел) по мере вычисления обновляются.
- 5 = 2 + 3
Сумма чисел - 5 (простое число), длина цепочки - 2.
- 17 = 2 + 3 + 5 + 7
Обновляем: сумма чисел - 17 (простое число), длина цепочки - 4.
Последний ответ, удовлетворяющий условиям задачи до миллиона - это ответ для цепочки, начинающейся с числа 2.
После чего проверим длины цепочек, начинающиеся с 3, 5 и 7:
- 2 + 3 + 5 + 7 …
- 3 + 5 + 7 + 11 …
- 5 + 7 + 11 + 13 …
Максимальная цепочка простых чисел оказалась среди них.
Ответ на задачу Эйлера
Ответ на 50 (юбилейную) задачу составил 997651 и вычисляется за 113 миллисекунд. Большая часть времени, думаю, ушло на вычисление списка простых чисел.
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали, злорадствовали)) и всячески помогали в саморазвитии.
Так же здесь Вы всегда можете подсмотреть правильный ответ на задачу Эйлера (иногда необходима небольшая подсказка), спросить совета более опытных (часто сам так и делаю) и посмотреть мой вариант решения (но сначала лучше попробовать решить самостоятельно).