Язык:
Язык:
Проект Эйлера 3 задача. Никаких чудес! Просто (прямо из штаб-квартиры Google) добываем секретный алгоритм и ответ получаем мгновенно.
Узнать больше в телеграм-канале: ProjectEuler++
Простые делители числа 13195 – это 5, 7, 13 и 29.
Какой самый большой делитель числа 600851475143, являющийся простым числом?
Если представить себе поиск ответа обычным перебором, то алгоритм представляется следующим:
Однако это уже 600 миллиардов операций!
При этом основной проблемой в задаче будет проверка, простые ли числа. Потому что, если следовать самому определению, число простое в том случае, если делится только на единицу и на само себя.
Чтобы в итоге проверить, простое ли число 5, понадобятся следующие операции:
Убедившись, что ни одно число не делит 5 нацело, можно сделать вывод, что оно простое.
Конечно, в программе эти операции будут выглядеть в виде одной строчки кода. Однако таким способом для проверки числа 600851475143 понадобится 600 миллиардов операций деления. А для числа перед ним (600851475142) еще 600 миллиардов операций.
Мы видим в итоге, что работа простого алгоритма потребует миллиарды миллиардов операций.
Для простоты объяснения идеи алгоритма программы возьмем не 600851475143, а меньшее число – 1000.
Число обратное простому называется составным и его можно разложить на множители.
Например 1000 = 2 * 500, и потому 1000 делится как на 2, так и на 500. При этом 2 – минимальный делитель числа, а 500 – максимальный.
Получается, максимальный делитель числа 1000 найден (500)? Однако простое ли это число (500)?
Для ответа нужно повторить цикл и попытаться разложить уже число 500 на множители. И делать так до тех пор, пока последний максимальный делитель в итоге перестанет раскладываться на множители.
Алгоритм получаем следующий:
Как мы видим в итоге тысяча тысяч операций по поиску максимального простого делителя числа 1000 сократилось до 5 итераций.
Именно в этой программе этот “лайфхак” не нужен, потому что алгоритм (выше) уже достаточно оптимизирует код. Однако задачи проекта Эйлер выстроены по мере нарастания сложности и цепляются друг за друга. Знания и навыки, выработанные в первых задачах, пригодятся в последующих. Потому можете считать это бонусом)
Возьмем небольшое число (12) и будем раскладывать его на множители:
Ясно видно, что первое и второе множества повторяют третье и четвертое. Только множители меняются местами.
Потому, чтобы определить простое ли число (12), можно не делить его на весь ряд чисел: 2, 3, 4… 10, 11. Достаточно проверить до корня квадратного из числа (sqrt(12) = 3.464). В данном случае это числа 2, 3, 4.
Для пятнадцатизначных чисел, например, ускорение работы в итоге будет кратное
Подключаем стандартную математическую библиотеку языка Си. Необходима для работы функции sqrt()
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. Время работы в итоге будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
В итоге ответ на 3 задачу проекта Эйлера составил 6857, программа работает быстро (ноль миллисекунд).
Однако для сравнения я пробовал работу наивного алгоритма. Даже после уменьшения проверяемого числа в сто раз, программа считала почти минуту.
P.S. Выражаю глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
