def is_perfect(n):
s = Decimal(1)
p = Decimal(2)
while p < n.sqrt()+1:
if n % p == 0:
s += p
if p != n/p: s += n/p
p += 1
return s == n
print(is_perfect(Decimal('137438691328')))
Запускаем, программа работает - число '137438691328' действительно является совершенным. Оно делится на 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524287, 1048574, 2097148, 4194296, 8388592, 16777184, 33554368, 67108736, 134217472, 268434944, 536869888, 1073739776, 2147479552, 4294959104, 8589918208, 17179836416, 34359672832 и 68719345664, сумма этих чисел равна 137438691328. Однако, на моем компьютере проверка “совершенности” данного числа заняла … 54 секунды. Это конечно быстро по сравнению с 16м веком, но совершенно недостаточно чтобы проверить все числа, хотя бы до миллиарда. Значит пора использовать более тяжелую артиллерию - перепишем программу на языке Си. Все-таки Python это интерпретатор, и работает заметно медленнее. Получаемый код не намного сложнее:
#include
#include
#include
#include
bool isPerfect(unsigned long long int n)
{
unsigned long long int sum = 1, i;
for(i=2; i<=sqrt(n)+1; i++)
{
if (n%i==0) {
sum += i;
if (i != n/i) {
sum += n/i;
}
}
}
return sum == n;
}
int main()
{
unsigned long long int n = 137438691328LL;
bool res = isPerfect(n);
printf("%d\n", res);
return 0;
}
Компилируем программу с помощью компилятора gcc, запускаем получившийся exe-файл: время выполнения меньше секунды, уже гораздо лучше. Теперь несложно поменять функцию main для перебора всех чисел от 1 до 200000000000. В код также добавлен вывод промежуточных результатов каждые 1000000 итераций, чтобы видеть ход выполнения программы.
int main()
{
unsigned long long int MAX = 200000000000LL;
unsigned long long int p;
for (p=1; p if (isPerfect(p))
printf(" %llu ", p);
if (p % 1000000 == 0)
printf("*%llu,%llu*", 100*p/MAX, p);
}
}
Увы, прогноз относительно скорости расчетов оказался слишком оптимистичным. Примерно за час работы программы, было перебрано лишь 100млн вариантов, а для перебора всех 200млрд понадобился бы не один день. Желающие могут продолжить процесс самостоятельно, однако с уверенностью можно сказать что в диапазоне от 1 до 100000000 действительно нет совершенных чисел кроме 6, 28, 496, 8128 и 33550336.