Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].
Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> #include <cmath> using namespace std; int main() { unsigned long long M; cin >> M; for (unsigned long long n = 4; n <= M; n += 2) { unsigned long long S = 1; for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) { if (n % j == 0) S += n / j + j; } if (n == S) cout << n << " "; } return 0; } |
Обратите внимание, что во внутреннем цикле мы прекращаем искать делители, если их сумма уже превышает исходное число.
Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [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] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Найти все чётные совершенные числа из unsigned long long #include <iostream> #include <cmath> using namespace std; // Подпрограмма определяет, является ли число n простым bool is_prime(unsigned long long n) { unsigned long long i = 3; while (i < sqrt(n)) { if (n % i == 0) return false; i += 2; } return true; } int main() { unsigned long long p = 1, n = 1; while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются p = 2 * n - 1; if (is_prime(p)) cout << n * p << " "; n <<= 1; } return 0; } |
Отметим, что это очень эффективный алгоритм: приведенные результаты были получены программой практически мгновенно. Программа из предыдущей задачи за разумное время этого сделать не может.
Вывод: если алгоритм плохой, то программа хорошей быть не может.
К сожалению, алгоритм не гарантирует нахождения всех совершенных чисел.