Как уменьшить время выполнения данной программы

Question

Как уменьшить время выполнения данной программы

Ksenia Знаток (271), закрыт 1 год назад

Как уменьшить время выполнения данной программы (чтобы было меньше 2с)
#include <iostream>
using namespace std;

int function(int a, int x=1)
{
if (x < a)
{
if (a % x == 0)
return x + function(a, x + 1);
else
return function(a, x + 1);
}
else
return 0;
}

int main()
{
int I, J, n = 0;
cin >> I >> J;
double s = 0, min = 10000;
for (int i = I; i <= J; i++)
{
s = function(i);
if (s/i <= min)
{
min = s/i;
n = i;
}
s = 0;
}
cout << n << endl;
return 0;
}

Answer 1

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

Answer 2

Для уменьшения времени выполнения данной программы можно использовать многопоточность. Один из способов - использовать std::async для запуска функции function(i) в отдельном потоке. Это позволит выполнять вычисления для каждого i параллельно. Однако, не стоит создавать слишком много потоков, так как это может привести к ухудшению производительности

Еще один способ - создать пул потоков и использовать его для выполнения функции function(i)
Это позволит избежать накладных расходов на создание и уничтожение потоков, что может ускорить выполнение программы.
Также можно использовать оптимизации в самой функции function, например, избежать повторных вычислений для одного и того же значения аргумента x
Наконец, можно использовать профилирование для выявления узких мест в программе и оптимизации их