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

344

24 декабря 2016, 16:47

#include <iostream>
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.

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

Answer 1

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

#include <iostream>
#include <iomanip>
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";
}

Answer 2

int sum=1, i;
for (i=3; i*i<n; ++i)
  if (!(n % i))
    sum += i + n/i;
if (!(n % i))
  sum += i;

Создание Интернет магазина Ивано-Франковск

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Некорректно работает goodFeaturesToTrack в третьей версии OpenCV

Пытаюсь найти особые точки кадра с помощью функции goodFeaturesToTrack в OpenCV 30:

366

c++

Не правильно вычисляет C++ [требует правки]

Задание:

308

MySQL

Вывести метки из БД и добавить на карту

Всем доброго времени суток!Скажите пожалуйста в чем ошибка, почему не выводятся метки на карту? Причем я проверил через Network и ответ приходит...

412

MySQL

Mysqli копирование данных из таблицы в таблицу

Есть две одинаковых таблицы: data_tmp и data у которых есть по одной записи

362