Совершенные числа

Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].

Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:

Обратите внимание, что во внутреннем цикле мы прекращаем искать делители, если их сумма уже превышает исходное число.

Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [latex]p = 2^{k+1}-1[/latex] простое, то число [latex]n = 2^k \cdot (2^{k+1}-1)=p \cdot 2^k[/latex] — совершенное ([latex]k = 1,2,\ldots[/latex]).
Функция prime() определяет, является ли число [latex]p[/latex] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.

Отметим, что это очень эффективный алгоритм: приведенные результаты были получены программой практически мгновенно. Программа из предыдущей задачи за разумное время этого сделать не может.
Вывод: если алгоритм плохой, то программа хорошей быть не может.
К сожалению, алгоритм не гарантирует нахождения всех совершенных чисел.

Related Images:

Добавить комментарий