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

Question

[yll3]

Есть код, как уменьшить время выполнения программы, чтобы было меньше одной секунды?

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
  int S=0,Smax=0,n,i,k;
  cin>>n;
  for(int i=1;i <= n;i++)
  {
   S=0;
   for(int j=1;j <= n;j++)
   {
    if(i%j == 0)
    S=S+j;
    if(S > Smax){Smax=S;k=i;}
   }
}
cout<<k;
return 0;
}

Answer 1

[Игорь Кальницкий]

Переписать алгоритм. А чтобы в этом вам помочь, для начала хотелось бы понять что делает данный алгоритм. На первый взгляд, это поиск числа от 1 до n, сумма делителей которого максимальная, верно?

Comments

[yll3]

Да, верно)

Answer 2

[T-D-K]

Нет смысла во втором цикле бежать до n. Как минимум можно бежать только до i, а ещё лучше до sqrt(i). И делать не S=S+j;, а S=S+j+i/j;
Это уже значительно ускорит работу программы. А если понять что корень возрастает медленно и не считать его для каждого i, а увеличивать на единицу переменную в которой хранится корень, то...

Answer 3

[JoyceGraham]

На первый взгляд почему бы не вынести
if(S > Smax){Smax=S;k=i;}
за пределы второго цикла? А то получается при каждом проходе идет проверка.