1 / 4
Feb 2011

The complexity of my algorithm is O(sqrt(n)) but still i am getting TLE ... dont know why...i there any better than that or should i use...some memoization

here is the q:
spoj.pl/problems/DIVSUM2/

#include<stdio.h>
#include<math.h>
#include<string.h>
void compute(long long k)
{
	long long sum=0;long long x=0;
	long long i;long long rt=sqrt(k);
	if(k==1){printf("%d\n",0); return;}      
    for(i=1;i<=rt;i++)
      {
	if(k % i ==0)
       {	  
	sum+=i;
		
  	x=k/i;
	if((x!=i)&&(x<=k/2))
	  sum+=x;	
		
    }

 }
	 			
printf("%lld\n",sum);
}
int main()
{
long long N;int tc;
scanf("%d",&tc);
while(tc--){
scanf("%lld",&N);
 compute(N);
}
return 0;
}
  • created

    Feb '11
  • last reply

    Feb '11
  • 3

    replies

  • 147

    views

  • 3

    users

  • 2

    links

Use pollard rho for factorization. O(sqrt(n)) will never pass.

can u give me any reliable link... where this algo is explained clearly...

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 14 7d

Want to read more? Browse other topics in C and C++ or view latest topics.