Dec 2016
2 / 7
Dec 2016
Jan 2017
vandana_98
Dec '16

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;

}

  • created

    Dec '16

  • last reply

    Jan '17
  • 6

    replies

  • 1.2k

    views

  • 2

    users

  • 1

    link

daft_wullie
Dec '16

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
Dec '16

Thanks for the help.

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

daft_wullie
Dec '16

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
Jan '17
#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.