# Need tips to Optimizing my code

I am stuck in TLE in Divisor Summation

Simply for each n find its divisors in O(sqrt(n))
https://www.codechef.com/viewsolution/34500416

brother can tell (give example) when this excute
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
sum+=i;
if(i!=n/i) <=== this one
sum+=n/i;
}
}

See when any no is perfect square then i will be to n/i if i=sqrt(n). So, not to add same no twice I have written that condition. Take n=9 and i=3

1 Like
``````lli spf[MAX+1];

void sieve2(){ //smallest prime factor of N.

loop(i,MAX+1) spf[i]=i;
for(lli i=4;i<=MAX;i+=2) spf[i]=2;

for(lli i=3; i*i<=MAX; i++){
if (spf[i] == i){
for (int j=i*i; j<=MAX; j+=i)
if (spf[j]==j) //marking spf[j] if it is not previously marked
spf[j] = i;
}
}
}

lli tfactor[MAX+1];
lli sumfactor[MAX+1];
void sieve4(){ // totalfactor and sum_of_all_factors
// n = (a^p)*(b^q)*(c^r)....
// totalfactors = (p+1)*(q+1)*(r+1)...
// sumoffactors =  [(a^(p+1)-1)/(a-1))]*[(b^(q+1)-1)/(b-1))]*[(c^(r+1)-1)/(c-1))]....
sieve2();
tfactor[1] = sumfactor[1] =1;
for(lli i=2;i<=MAX;i++){
lli mspf = spf[i];
lli prim = mspf;
lli temp = i;
lli cnt=0;
while(temp%mspf==0){
temp/=mspf;
cnt+=1;
prim = prim*mspf;
}
tfactor[i] = (cnt+1) * tfactor[temp];
sumfactor[i] = (prim -1)/(mspf-1) * sumfactor[temp];
}
}
int main(){
fastio
lli t=1;
sieve4();
cin>>t;
while(t--) {
lli n;
cin>>n;
cout<<sumfactor[n]-n<<endl;
}
return 0;
}
``````

brother can you explain me the logic

Read my comment in sieve4 function

sorry bro but what is MAX??

@codedirector usually a safe number, which is greater than the input constraints.
like if you are asked to create an array of 10 elements than to be at safe usually people create a variable or define as:
int MAX = 15
or
#define MAX 15
so here MAX represent the maximum value that can be provided in the input

MAX is Upper limit in this 500001

Here my AC solution : https://www.codechef.com/viewsolution/33637053

thanks brother as I donâ€™t have idea about it.

bro remove extra code.
I think you have paste all your code on a single page.

Thatâ€™s my way â€¦BTW i gave u main code in above comment

@codedirector â€śextra codeâ€ť isnâ€™t what @ssrivastava990 is using.
To see what is â€śextra codeâ€ť check this : https://www.codechef.com/viewsolution/34147880 .
I actually bookmarked this to copy templates in future.

Man around 2k lines

1 Like