Project Euler (answers)

Проект Эйлера: Ответ и решение 12 задачи (Треугольное число с большим количеством делителей)

Проект Эйлера (12 задача) не требует навороченного алгоритма вычисления, однако чтобы найти ответ за приемлемое время потребуются ухищрения.

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

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

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-е треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Перечислим делители первых семи треугольных чисел:
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
Как мы видим, 28 – первое треугольное число, у которого более пяти делителей.
Каково первое треугольное число, у которого более пятисот делителей?

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

Описание работы программы

Вычисляем треугольные числа
Считаем делители числа

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

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

Вычисляем треугольные числа

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

Так 6-е треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 = 21.
В то время как 7-е треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Потому что можно сделать проще – к предыдущему треугольному числу прибавлять натуральное таким образом:

6-е треугольное число равно 5-е число (15) + 6 = 21;
7-е треугольное число равно 6-е (21) + 7 = 28;
и так далее.

Считаем делители числа

Самым простым способом будет перебрать все делители от единицы до самого числа и те, которые делятся нацело, посчитать.

Однако вычисляться это будет целую вечность. Потому применим несколько хитростей (смотрите выше).

Во-первых, если число имеет делитель, то его можно разложить на два числа. Возьмем, для примера число 36:

36 % 1 == 0 следовательно 36 = 36 * 1;
36 % 2 == 0 => 36 = 18 * 2;
36 % 3 == 0 => 36 = 12 * 3;
36 % 4 == 0 => 36 = 9 * 4;
36 % 6 == 0 => 36 = 6 * 6;

Потому, получая делитель числа 1 (назовем его минимальный) мы сразу же получаем второй делитель – 36 (максимальный), для 2 получаем 18, 3 – 12 и так далее.

Во-вторых, после квадратного корня из числа делители начнут повторяться (для числа из примера 36 – после 6). Потому подсчет делителей идет только до sqrt() из числа.

В-третьих, функцию sqrt() необходимо вынести перед циклом for. Это необходимо делать потому, что некоторые компиляторы будут вычислять sqrt() на каждой итерации цикла. Конкретно для моего компилятора и этой конкретной задачи разница во времени работы программы составила в двадцать раз.

В-четвертых, иногда число раскладывается на два одинаковых числа (36 = 6 * 6). Потому этот случай необходимо считать как один найденный делитель.

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

math.h

Подключаем стандартную математическую библиотеку языка Си. Необходима для работы функции sqrt()

int max_div = sqrt(triple)

Функция sqrt(triple) возвращает квадратный корень из triple(внимание!) в вещественном виде.
int max_div = sqrt(triple) – присваиваем вычисленное значение переменной max_div (внимание!) в целочисленном виде.
Т.е. от числа вида 12.34567 отбрасывается дробная часть – 12
Это необходимо т.к. for() работает только с целочисленными значениями

div++

То же самое, что div = div + 1

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

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

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

В итоге ответ на 12 задачу проекта Эйлера составил 76576500, программа работает довольно быстро – примерно 100 миллисекунд.

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

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

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

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

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