Project Euler (answers)

Проект Эйлера: Ответ и решение 5 задачи (Наименьшее кратное)

Проект Эйлера (5 задача) потребует минимального знания математики (класса восьмого). Но при решении лучше воспользоваться алгоритмом Евклида.

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

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

2520 – самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?

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

Используем алгоритм Евклида для нахождения наибольшего общего делителя.

Функция для определения наибольшего общего делителя (алгоритм Евклида – итеративная версия).
Функция для определения наибольшего общего делителя (алгоритм Евклида – рекурсивная версия).

Определяем наименьшее общее кратное.

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

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

Используем алгоритм Евклида для нахождения наибольшего общего делителя - проект Эйлера (5 задача)

Функция для определения наибольшего общего делителя (алгоритм Евклида - итеративная версия)

Для решения данной задачи проекта Эйлера понадобится находить наибольший общий делитель чисел. Эффективно это делать с помощью алгоритма Евклида (смотрите выше).

Общий смысл алгоритма легче объяснить на численном примере.

Найдем НОД двух чисел: 645 и 381.

Пара чисел делится друг на друга (всегда большее на меньшее).

645 / 381 = 1 (остаток 294)

Большее из чисел в паре заменяется на полученный остаток от деления

381 / 294 = 1 (остаток 87)
294/ 87= 3 (остаток 33)

В итоге цикл происходит до тех пор пока, одно из чисел (остаток от деления) не станет равен нулю.

33/ 3= 11 (остаток 0) – НОД найден (3)

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

long long num1

Тип переменной num1 – long long int (максимум плюс-минус девятнадцатизначное число)

while(num1 && num2)

Оператор цикла while(условие){действия} выполняет действия указанные в {фигурных скобках} до тех пор пока (условие) истинно (true).
(значение) – если в скобках не условие, а значение, то любое ненулевое значение будет восприниматься как истина (true)
(num1 && num2) – true только, если оба значений истинны (true и true). В контексте нашей задачи – оба значения ненулевые.

num1 %= num2

То же самое, что

num1 = num1 % num2

return (num1 > num2) ? num1 : num2;

Условное тернарное выражение. Если num1 больше num2, то вернет num1, иначе – num2.

Функция для определения наибольшего общего делителя (алгоритм Евклида - рекурсивная версия)

Однако так же можно воспользоваться и рекурсивным алгоритмом Евклида. Потому разберем пример.

Найдем НОД двух чисел: 29 и 9.

Пока один из аргументов функции не будет равным нулю, она будет вызывать сама себя таким образом:

get_NOD(29,9) -> get_NOD(9,6) -> get_NOD(6,3) -> get_NOD(3,0) -> НОД равен 3.

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

29 % 9 = 6 -> 9 % 6 = 3 -> 6 % 3 = 0

Однако при данной реализации функции необходимо изначально правильно подать аргументы (num2 > num1). В итоге дальше максимальный аргумент выбирается автоматически – постоянной заменой их местами при вызове функции.

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

if(!num1 || !num2)

Оператор цикла if(условие){действия} выполняет действия указанные в {фигурных скобках} в том случае, если (условие). истинно (true).
if(num1) – если в скобках не условие, а значение, то любое ненулевое значение будет восприниматься как истина (true).
if(!num1) – операция ! инвертирует логическое значение (true в false и наоборот). В данном случае true будет при нулевом значении переменной.
(!num1 || !num2) – true только, если одно из значений истинно (true или true). В контексте нашей задачи – одно из значений нулевое.

num2 % num1

Возвращает остаток от деления num2 на num1.

return (num1 > num2) ? num1 : num2;

Условное тернарное выражение. Если num1 больше num2, то вернет num1, иначе – num2.

Определяем наименьшее общее кратное - проект Эйлера (5 задача)

Что может быть проще, чем найти число, которое делится без остатка, к примеру, на 2 и 3?

2 * 3 = 6 – вот и все

Однако для составных чисел (т.е. которые можно разложить на множители) не все так просто.

4 * 6 = 24 – верно, но оно не является минимальным. Потому что 12 можно разделить и на 4 и на 6.

В итоге для нахождения наименьшего общего кратного существует универсальная формула:

НОК(a,b) = a*b/НОД(a,b)

Где НОД – наибольший общий делитель (смотрите выше).

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

long long num1

Тип переменной num1 – long long int (максимум плюс-минус девятнадцатизначное число)

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

Используя упомянутые выше функции, в цикле for() ищем НОК следующих пар чисел:

answ = 1.

answ = НОК(1,2) = 2
answ = НОК(2, 3) = 6
answ = НОК(6,4) = 12
answ = НОК(12,5) = … и так далее

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

printf("%lld", answ);

Функция printf() служит для форматированного вывода.
%d – спецификатор преобразований преобразует информацию к необходимому виду. В данном случае указывает на целое число со знаком в десятичной форме.
ll – суффикс указывающий на тип числа. В данном случае %lld указывает на тип long long int.

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

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

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

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

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

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

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

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

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