How to reduce the execution time of the program?

There is code to reduce the run time to less than one second?
#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; }< code></k></cstdio></iostream>
October 3rd 19 at 01:45
3 answers
October 3rd 19 at 01:47
Solution
To rewrite the algorithm. And to help, for a start I would like to understand what makes this algorithm. At first glance, this search numbers from 1 to n, the sum of the divisors of which is the maximum, right?
Yes, that's right.) - Reagan_Bins68 commented on October 3rd 19 at 01:50
October 3rd 19 at 01:49
Solution
There is no sense in the second cycle to run to n. At least you can run only before i, and even better to sqrt(i). And do not S=S+j; and S=S+j+i/j;
It already will speed up the program. And if you understand what root is growing slowly and not to consider him for each i, and to increment a variable which stores the root, the...
October 3rd 19 at 01:51
At first glance, why not make
if(S > Smax){Smax=S;k=i;}
beyond the second cycle? And it turns out in each iteration there is a check.

Find more questions by tags C++Programming