CODEWITHSUNDEEP
c++numberstime-complexity
Bhavya Bhatia
Bhavya Bhatia

Reputation: 53

Is there any way to reduce execution time of this code?

I am trying to find the sum of all the divisors of a given number But I am exceeding the time limit,help me to reduce the time limit of this code. 

int a,count=0;
cin>>a;
for(int i=2;i<=a/2;i++) {
    if(a%i==0) {
        count=count+i;
    }
}
count++;
cout<<count;

Upvotes: 0

Views: 122

Answers (4)

Bhavya Bhatia
Bhavya Bhatia

Reputation: 53

Thanks everyone for the help..I got the answer

     bool  is_perfect_square(int n) 
     {
     if (n < 0)
     return false;
     int root(round(sqrt(n)));
     return n == root * root;
     }
     main()
     {
     int t;
     cin>>t;
     while(t--)
    {
    int a,count=0;
    cin>>a;
    bool c=is_perfect_square(a);


    for(int i=2;i<=sqrt(a);i++)
    {
        if(a%i==0)
        {
            count=count+i+a/i;

        }

    }
    if(c==true)
    {
                count = count - sqrt(a);
    }
    count++;
    cout<<count<<endl;
    }


}

Upvotes: 0

Sumeet Kumar Yadav
Sumeet Kumar Yadav

Reputation: 12985

This problem can be optimized by prime factorization .

Let’s assume any number’s prime factor is = a ^n*b^m*c^k
Then, Total number of devisors will be = (n+1)(m+1)(k+1)
And sum of divisors = (a^(n+1) -1 )/(a-1)  *  (b^(m+1)-1)/(b-1) *(c^(k+1)-1)/(c-1)
X = 10 = 2^1 * 5^1
Total number of devisors = (1+1)(1+1) =2*2= 4
Sum of divisors  = (2^2 – 1 ) /1 * (5^2 -1 )/4 =  3 * 24/4  =  18
1+2+5+10 = 18

Upvotes: 0

Imran
Imran

Reputation: 413

I would say go up to sqrt(a). Each time you have a remainder 0, add both the i and a/i. You will need to take care of the corner cases, but this should bring down the time complexity. Depending on how large a is this should be faster. For small values this may actually be slower.

Upvotes: 1

Semyon Burov
Semyon Burov

Reputation: 1172

You can make loop run to sqrt(a), not a / 2 if you would sum two divisors at time: count += i + a / i

Upvotes: 3

Related Questions