SPOJ : DIVSUM Solution

Spoj:  DIVSUM Solution


#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

int main()
{
int divisor[500002];    //creating array to store divsum 
                                     //of all numbers till 500001 
int t,i=0,j=0,n=0;

for(i=1;i< 500002;i++)
{
    for(j=2*i;j< 500002; j+=i){
        divisor[j]+=i;                  
    }                                  
}

for(scanf("%d",&t);t>0;t--){
    scanf("%d",&n);
    printf("%d\n",divisor[n]);
}
return 0;
}

EXPAINATION :

  To create the array of divsum ,  do it the same way as in Sieve of Eratosthenes. That is, first mark all multiple of 2 except 2*1 ,   then mark all multiples of 3 except 3*1 i.e starting from 3*2 and then mark all multiples of 4 except 4*1 ie starting fron 4*2 and so on....