DIVSUM Time limit exceeded

[vandana_98]

hi,
i m having some problem with the DIVSUM(divisor summation) program. Its giving me time limit exceeded.

Can someone please help me with the code to reduce the time of execution.

include

using namespace std;

int main()
{
int t,a,i,l,sum;
scanf("%d",&t);
while(t--)
{ scanf("%d",&a);
sum=0;

		for(i=1;i<=a/2;i++)
		{	if(a%i==0)
			{	sum=sum+i;
			}
		}
	printf("%d\n",sum);

}
return 0;

}

[daft_wullie]

There is a bunch of optimization strategies which can be used here. And that is typical for SPOJ problems: It is easy to implement a bruteforce algo (like yours), but can become very difficult to find an efficient algorithm.

I solved this problem using prime generation, generating prime factors and summing up all possible prime combinations. And I did not get a good time ...

The most obvious approach for your code is the fact, that you always find two divisors, not just one. Considering this your for loop only needs to run up to sqrt(a).

[vandana_98]

Thanks for the help.

Considering this your for loop only needs to run up to sqrt(a).

Could you please elaborate because i m not able to understand to how to proceed further.

[daft_wullie]

Could you please elaborate

Take a look at this simple python sample:

""" Demonstrate sum of divisors"""
from __future__ import print_function, division
from math import sqrt


def divisor_sum_naive(number):
    """ return sum of divisors, naive algorithm """
    divisor_sum = 0
    for candidate in range(1, number // 2 + 1):
        if not number % candidate:
            divisor_sum += candidate
    return divisor_sum

def divisor_sum_pairwise(number):
    """ return sum of divisors, pairwise divisors """
    divisor_sum = 1
    limit = int(sqrt(number))
    for candidate in range(2, limit + 1):
        if not number % candidate:
            divisor_sum += candidate
            if candidate * candidate != number:
                divisor_sum += number // candidate
    return divisor_sum


def main():
    """ main function """
    for number in range(1, 100):
        print(number, divisor_sum_naive(number), divisor_sum_pairwise(number))

if __name__ == '__main__':
    main()

divisor_sum_naive() is your approach, divisor_sum_pairwise() is what I meant.

[vandana_98]

#include <iostream>
#include<math.h>
using namespace std;

int main() 
{
	
	void sum(int,int);
	int t,a,l;
	scanf("%d",&t);
	while(t--)
	{	scanf("%d",&a);
		l=sqrt(a);
		sum(a,l);
	}
	return 0;
}
void sum(int a,int l)
{       int i,sum=1;
		
	for(i=2;i<=l;i++)
		{	if(a%i==0)
			{	sum=sum+i;
				if(i*i!=a)
					{sum=sum+a/i;
					}
			}
		}
		printf("%d\n",sum);
}

I submitted this code in SPOJ, its giving me a wrong answer but code ran in ideone successfully. I m not able to understand the error in the code.

[daft_wullie]

oh, there is an error in my code, it is wrong for the input 1. Sorry

[vandana_98]

I got the code accepted.Thanks for the help