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>
```

asked October 3rd 19 at 01:45

3 answers

answered on

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

answered on

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...

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...

answered on October 3rd 19 at 01:51

At first glance, why not make

beyond the second cycle? And it turns out in each iteration there is a check.

`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