Project Euler (answers)

Язык:

Проект Эйлера: Ответ и решение 1 задачи (Числа, кратные 3 или 5)

Проект Эйлера 1 задача – имеет уровень сложности типичный для “Hello world”, потому решил ее сразу двумя способами.

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

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

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Найдите сумму всех чисел меньше 1000, кратных 3 или 5.

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

Первый вариант решения задачи

Примечания

Второй вариант решения задачи

Ответ на задачу Эйлера и скорость работы программы

Первый вариант решения - проект Эйлера (1 задача)

Создаем переменную res, в которую будем сохранять искомую сумму чисел.
В цикле for перебираем числа от 1 до 999 включительно.
Если число делится на 3 или 5, (условие задания) то оно плюсуется к переменной res.
В итоге, с помощью функции printf(), выводим ответ на экран.

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

i % 3 == 0

4 % 3 – возвращает остаток от целочисленного деления 4 на 3, т.е. 1
Если остаток от деления двух чисел равен нулю, то числа делятся нацело.
i % 3 == 0 – сравнение на равенство, если остаток от деления равен нулю, то вернет true (истина), иначе – false (ложь)

условие 1 || условие 2

|| – операция сравнения “или“
Вернет true (истина), если одно из условий истинно, иначе – false (ложь)

if (!(i % 3))

(i % 3) – любое ненулевое число внутри оператора if() будет восприниматься как true (истина).
Условие будет срабатывать и будет работать код после if()
! – операция “не” инвертирует значение true в false и наоборот.
Таким образом if (!(i % 3)) – сработает если остаток от деления будет равен нулю, следовательно числа делятся нацело

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

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

Второй вариант решения - проект Эйлера (1 задача)

Перебираем числа, изменяя счетчик цикла сразу по три: 0… 3… 6… 9… и так далее до 999.
Сразу прибавляем их к результату, потому что все они делятся на три.
Далее изменяем счетчик цикла сразу по пять: 0… 5… 10… 15… и так далее до 999.
Их тоже прибавляем к сумме, потому что все они делятся на пять.
Число 15 делится одновременно и на 3 и на 5, поэтому число 15 и потому кратные ему будут занесены в сумму дважды.
Вычитаем из суммы числа, кратные 15.
Однако скорость вычислений особо не изменилась.

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

В итоге ответ на 1 задачу проекта Эйлера составил 233168.

Программа работает не просто быстро – мгновенно (ноль миллисекунд).

Я пробовал увеличить объем вычислений на несколько порядков – однако скорость оставалась неизменной. В итоге пришел к выводу, что задача пока что слишком простая.

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

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

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

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

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