Улучшить скорость работы программы С++

#cpp #алгоритм

#include 

using namespace std;

int sum_of_dil(int n)
{
    int sum = 0;
    if (n%2==0)
    {
        for(int i=1;i<=n/2;++i)
            if (n%i ==0) sum += i;
    }
    else
    {
        for(int i=1;i<=n/2;i+=2)
            if (n%i ==0) sum += i;
    }

    return sum;
}

int main()
{
    int a, b;

    int count = 0;
    cin >> a >> b;

    for(int i=a;i<=b;++i)
    {
        for(int j=i+1;j<=b;++j)
        {
            if (sum_of_dil(i) == j && sum_of_dil(j) == i)
            {
                cout << i << " " << j << endl;
                count++;
            }
        }
    }


    if (count ==0) cout << "Absent" << endl;
    return 0;
}


Задача отсюда -> Тык


  Два различных натуральных числа называются дружественными, если первое
  из них равна сумме делителей второго числа, за исключением самого
  второго числа, а второе равно сумме делителей первого числа, за
  исключением самого первого числа. Нужно найти все пары дружественных
  чисел, оба из которых принадлежат промежутку от M до N.


Не проходит по времени.
    

Ответы

Ответ 1

Просвистело за 2мс: :)

#include 
#include 

using namespace std;

struct Frd
{
    int a, b;
} f[] =
{
    { 220,284 },
    { 1184,1210 },
    { 2620,2924 },
    { 5020,5564 },
    { 6232,6368 },
    { 10744,10856 },
    { 12285,14595 },
    { 17296,18416 },
    { 63020,76084 },
    { 66928,66992 },
    { 67095,71145 },
    { 69615,87633 },
    { 79750,88730 },
    { 100485,124155 },
    { 122265,139815 },
    { 122368,123152 },
    { 141664,153176 },
    { 142310,168730 },
    { 171856,176336 },
    { 176272,180848 },
    { 185368,203432 },
    { 196724,202444 },
    { 280540,365084 },
    { 308620,389924 },
    { 319550,430402 },
    { 356408,399592 },
    { 437456,455344 },
    { 469028,486178 },
    { 503056,514736 },
    { 522405,525915 },
    { 600392,669688 },
    { 609928,686072 },
    { 624184,691256 },
    { 635624,712216 },
    { 643336,652664 },
    { 667964,783556 },
    { 726104,796696 },
    { 802725,863835 },
    { 879712,901424 },
    { 898216,980984 }
};


int main(int argc, const char * argv[])
{
    int M, N;
    cin >> M >> N;
    int count = 0;
    for(unsigned int i = M>>15; i < sizeof(f)/sizeof(f[0]); ++i)
    {
        Frd x = f[i];
        if (x.a >= M)
        {
            if (x.b <= N)
            {
                ++count;
                cout << x.a << " " << x.b << endl;
            } else break; 
        }
    }
    if (count == 0) cout << "Absent\n";
}


Ответ 2

int sum=1, i;

for (i=3; i*i