Найти все совершенные числа, меньшие N

Рейтинг: 0Ответов: 2Опубликовано: 06.10.2014

Помогите. Столкнулся с очень странной проблемой своего рода. На лабораторную дали задачу. Теоретически все правильно написал, но, к сожалению, ответ выводится не всегда. Посмотрите, пожалуйста, в чем ошибка. Заранее спасибо!

Найти все совершенные числа, меньшие N. Число называется совершенным, если оно равно сумме всех своих делителей за исключением самого числа. Например, 6=1+2+3

Вот сам код, который, к сожалению, не работает:

#include <stdio.h>
#include<math.h>
#include<locale.h>
void main()
{
setlocale(LC_ALL,"RUSSIAN");
int N,i=1,sum=0,n=1;
printf("введите N\n");
scanf("%d",&N);
for (i=1;i<N;i++)
{
for (n=1;n<i;n++)
{
if (i%n==0)
sum=sum+n;
}
if (i==sum) printf("совершенное %d\n", i);
}
}

Программа на Си.

c#
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Вы забываете обнулять сумму делителей, в результате чего она постепенно накапливается. Исправьте ваши циклы примерно так:

for (i = 1; i<N; i++)
{
    sum = 0;  // обнуление суммы делителей
    for (n = 1; n<i; n++)
    {
        if (i%n == 0)
            sum = sum + n;
        }
        if (i == sum) 
        printf("совершенное %d\n", i);

    }

Кстати, в плане производительности алгоритм может быть существенно улучшен, например, тем, что во втором цикле условием остановки можно указать не n < i , а n <= i/2, поскольку очевидно, что все целые делители числа не больше половины этого числа

▲ 1

Не существует нечётных совершенных чисел меньше 10**1500 (единичка и полторы тысячи нулей) [Odd perfect numbers are larger than 10**1500 (2012)]. Для сравнения, самое большое число типа int имеет меньше чем 20 десятичных цифр (64bit int).

Все чётные совершенные числа равны Mp *(Mp + 1) / 2, где Mp -- простое число Мерсенна (2**p - 1). Поэтому все чётные совершенные числа в двоичной записи содержат сначала p единиц, за которыми следует p—1 нулей:

110
11100
111110000
1111111000000
1111111111111000000000000
111111111111111110000000000000000
1111111111111111111000000000000000000
1111111111111111111111111111111000000000000000000000000000000
...

где p равны 2, 3, 5, 7, 13, 17, 19, 31. На настоящее время (2013), известно только 48 таких чисел. Используя простую таблицу и библиотеку, поддерживающую арифметику с большими числами (чтобы десятичное представление легко напечатать), можно написать программу, которая выводит все известные совершенные числа меньше заданного числа.

Все чётные совершенные числа известны до числа с 18304103 десятичных цифр
(ceil((p+(p-1))*log10(2))). Cамое большое известное совершенное число 1692963953...6270130176 имеет 34850340 десятичных цифр -- если это число в книжку записать, то по размеру примерно десять "Война и миръ" получится.