Project Euler (answers)

Проект Эйлера: Ответ и решение 23 задачи (Неизбыточные суммы)

Проект Эйлера (23 задача) решается довольно быстро, если не вычислять одно и то же повторно, а сохранить промежуточные результаты в массив.

Узнать больше в телеграм-канале: ProjectEuler++

Условия задачи

Совершенным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является совершенным числом.
Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.
Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.
Найдите сумму всех положительных чисел, которые не могут быть записаны как сумма двух избыточных чисел.

Содержание статьи

Решение задачи

Измеряем время работы программы

Используемые при расчете функции

Функция, которая возвращает сумму делителей числа
Функция, которая определяет избыточное число
Функция, которая определяет может ли быть число записано как сумма двух избыточных чисел

Ответ и скорость работы программы

Решение (проект Эйлера - 23 задача)

Для проверки каждого числа на соответствие условиям задачи нам понадобится проверять пары чисел вплоть до него самого. Потому к каждому числу мы будем обращаться многократно. Это в итоге приведет к многократным повторным проверкам чисел на то, являются ли они избыточными. Потому лучше вычислить их состояние один раз и сохранить.

Для этого воспользуемся массивом, индексом которого будет являться число, а значением – признак “избыточное” / “неизбыточное”:

массив[число] = 1; // число избыточное
массив[число] = 0; // число неизбыточное

В итоге задача решается буквально в два действия:

заполняется массив избыточных чисел;
для каждого числа менее 28123 проверяется соответствие условиям задачи.

Описание работы самих функций ниже по тексту.

Измеряем время работы программы

Для измерения времени работы программы подключаем библиотеку time.h:

#include <time.h>

С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.

* Примечания:

clock_t

clock_t это тип данных, определенный через typedef. По сути это обычный целочисленный long

(double)

(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)

CLOCKS_PER_SEC

CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000

Используемые при расчете функции (проект Эйлера - 23 задача)

Функция, которая возвращает сумму делителей числа

Многократно обсужденная функция для поиска делителей числа. Однако повторю ее основные особенности:

Любое число делится нацело на 1, потому сразу заносим его в сумму.
Как только найден делитель (например, 12%2 == 0), сразу находится второй делитель (больший – 12/2 = 6).
Потому не стоит перебирать делители вплоть до самого числа. Вполне достаточно идти только до корня квадратного из проверяемого числа. Потому что дальше делители будут просто повторяться.
Вычисление квадратного корня лучше вынести перед циклом, чтобы избежать его вычисления на каждой итерации.
В случае, если делитель (16%4) и больший делитель (16/4) совпадают, следует занести только один делитель.

Функция, которая определяет избыточное число

Функция следует прямо заданию:

вернет true, если сумма делителей в итоге больше числа;
иначе вернет false.

Функция, которая определяет, может ли быть число записано как сумма двух избыточных чисел

В задании указано, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Потому, если число является большим, функция сразу вернет true.

Такие числа в задаче мы использовать не будем, однако функцию захотелось сделать максимально полной.

В функции перебираются числа num, вплоть до проверяемого числа number.

Статус num уже не вычисляется, а просто берется из массива с заранее вычисленными данными.
Если num – избыточное число, то в таком случае проверяется его пара (number – num).
Как только пара избыточных чисел находится, цикл прерывается и возвращается – true.
false вернется, если таких для данного числа пар нет.

Ответ и скорость работы программы (проект Эйлера - 23 задача)

В итоге ответ на 23 задачу проекта Эйлера составил 4179871, программа считает ответ мгновенно – за 0.0000000 секунды.

По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.

Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))

Есть вопросы, господа?

Политика конфиденциальности

Конфиденциальность