Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Проверка числа но совершенность

Автор: vx92 19.12.2007, 15:10

Код


//Проверка числа но совершенность(Совершенное число это такое число 
//сумма делитилей которго равна самому числу, например: 1+2+3=6)
#include <iostream>

using namespace std;

int main()
{
    int m = 0, sum = 0;
    cin >> m;
    for(int i = 1; i<m; i++)
    {
        if(m%i == 0)
        {
            sum += i;
        }
    }
    if(sum==m)
    {
        cout << "Da!\n";
    }
    else
    {
        cout << "Net!\n";
    }
    return 0;
}

Автор: Fin 19.12.2007, 17:08

Можно еше улучшить алгоритм. Не имеет смысл проверять делители, которые больше, чем исходное число деленное на два. При делении, получается второй делитель. Его также можно учитывать. smile

Автор: vx92 19.12.2007, 19:21

Ok! Спасибо за совет!

Автор: vx92 19.12.2007, 19:55

Ты это имел ввиду:

Код


//Проверка числа но совершенность(Совершенное число это такое число 
//сумма делитилей которго равна самому числу, например: 1+2+3=6)
#include <iostream>

using namespace std;

int main()
{
    int m = 0, sum = 0, n =0;
    cin >> m;
    n = m/2;
    sum += n;
    for(int i = 1; i<n; i++)
    {
        if(m%i == 0)
        {
            sum += i;
        }
    }
    if(sum==m)
    {
        cout << "Da!\n";
    }
    else
    {
        cout << "Net!\n";
    }
    return 0;

}

Автор: Fin 20.12.2007, 01:10

Что то типа этого:

Код


#include <iostream>
using namespace std;

bool IsIdeal(int m)
{
    int sum = 1, up =0, down=2;
    up = m/2;
    while(down<up)
    {        
        if(m%down == 0)
        {
            sum += down;
            up=m/down;
            sum += up;
        }
        down++;
    } 

    return (sum==m);
}

int main()
{
    for(int i=2; i<1000; i++)
    {
       if (IsIdeal(i)) cout << i << endl;
    }    
    return 0;
}

Автор: Fin 20.12.2007, 01:43

Вот более с оптимизированный код:

Код


#include <iostream>
using namespace std;

bool IsIdeal(int m)
{
    int sum = 1, down=2, up=m/down;;
    while (down<up)
    {   
        if(m%down == 0)
        {
            sum += down;
            sum += up;
        }
        down++;
        up=m/down;     


    } 

    return (sum==m);
}

int main()
{
    for(int i=2; i<1000000; i++)
    {
       if (IsIdeal(i)) cout << i << endl;
    }    
    return 0;
}

Поставил с засечкой времени у себя на машине

Цитата

time ./main
6
28
496
8128

real    0m25.004s
user    0m24.994s
sys     0m0.000s