А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...

Всем привет! Сегодняшняя пачка задачек небольшая, но весьма древняя – им более 2 тысяч лет. Известно даже имя математика, который их тогда и решил – это Евклид. И задачки эти посвящены так называемым «совершенным числам», то есть таким, которые равны сумме всех своих делителей. Например, 6 = 1+2+3. Или 28 = 1+2+4+7+14. Вот такая сегодня математическая археология -> Задачка 1. Евклид доказал, что если 2n - 1 - простое число, то 2(n - 1) * (2n - 1) - совершенное (n - натуральное число, само собой)...