Project Euler (answers)

Проект Эйлера: Ответ и решение 21 задачи (Дружественные числа)

Проект Эйлера (21 задача) внешне крайне простая, однако она имеет широкие возможности для оптимизации и ускорения.

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

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

Пусть d(n) определяется как сумма делителей n (числа меньше n, делящие n нацело).
Если d(a) = b и d(b) = a, где a ≠ b, то a и b называются дружественной парой, а каждое из чисел a и b – дружественным числом.
Например, делителями числа 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, поэтому d(220) = 284. Делители 284 – 1, 2, 4, 71, 142, поэтому d(284) = 220.
Подсчитайте сумму всех дружественных чисел меньше 10000.

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

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

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

Функция для расчета суммы делителей числа

Контролируем корректность работы функций

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

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

Будем сохранять вычисления, потому что это позволит не вычислять одно и тоже повторно и в итоге сократит время работы программы. Для этого создадим массив, в котором будем хранить суммы делителей числа по их индексу.

Далее алгоритм простой (смотрите выше).

перебираются числа до 10000;
с помощью функции get_sum_div() вычисляются их суммы делителей;
и заносятся в массив.

Например, сумма делителей числа 220 равна 284.

div_arr[220] = 284

При этом сразу же каждое число проверяем на то, нет ли у него дружественных чисел (смотрите задание). Для этого обращаемся к массиву. Например, для числа 284:

arr[284] = 220

Сумма делителей числа 284 это 220. И такая конструкция:

arr[arr[284]]

…будет означать:

arr[220] (массив вернет 284)

Проверив, после чего, числа на неравенство:

220 != 284

Получаем в итоге, что числа 284 и 220 являются дружественными. Прибавляем потому их к искомой сумме.

При этом пары чисел не будут дублироваться (284 и 220) и (220 и 284). Так будет происходить, потому что когда перебор чисел доходит до меньшего из пары дружественных чисел (220), сумма делителей большего (284) еще не вычислена значение в массиве равно нулю.

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

iso646.h

#include <iso646.h> подключает заголовочный файл, позволяющий использовать альтернативные формы написания логических операций:

and (&&)
and_eq (&=)
bitand (&)
bitor (|)
compl (~)
not (!)
not_eq (!=)
or (||)
or_eq (|=)
xor (^)
xor_eq (^=)

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

Для измерения времени работы программы подключаем библиотеку 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

Функция для расчета суммы делителей числа (проект Эйлера - 21 задача)

Функция перебирает делители числа и суммирует их. При этом:

Поскольку любое число делится на один, то счет начинаем сразу с него.
При нахождении делителя числа, автоматически находится второй.
Так, например, 12 / 2 = 6. Потому найдя делитель 2 (меньший), мы автоматически находим еще один делитель – 6 (больший).
Нет необходимости перебирать все делители вплоть до проверяемого числа, достаточно проверить до корня квадратного из него.
Так при поисках делителей числа 12 достаточно проверять делители до 3 – дальше пары делителей повторяются:
2 * 6
3 * 4
4 * 3
6 * 2
Выносим функцию вычисления квадратного корня sqrt() перед циклом for(). Делаем так потому, что иначе вычисления sqrt() будут производиться на каждой итерации.

Контролируем корректность работы функций

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

if (num < 1)

В итоге значения чисел, выходящие за рамки, на которые рассчитана функция, она считать не будет и сразу вернет 0.

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

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

В итоге ответ на 21 задачу проекта Эйлера составил 31626, программа считает ответ мгновенно.

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

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

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

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

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