divisors count sum gives time consuming issue

Question

I want to write divisors of all numbers between 1,...,n for a given n and then out the number of them and the sum of them. For example: For 3: 1,1,2,1,3 Output is 5, 8 I tried to get every j in range 1,n and then count the number of divisors by using the below code but the it is not efficient because of time consuming.

int count=0;
int sum=0;
for(int j=1,j<=n,j++){
    for(int i=1,i<=j,i++){
        if(j%i==0){
            count+=1;
            sum+=i;
        }
    }
}

Answer 1

It's a famous problem so should have been asked before. Instead of getting each number and then finding its divisors, you can simply count how many numbers are multiple of each number in that range.

---

that is [n/i]. so each number i in {1,...,n} appears [n/i] times. what remains for counting the number of them is summing this for all i in the range and summing i*[n/i] for the sum. This code does what you want:

---

Instead of getting each number and then finding its divisors, you can simply count how many numbers are multiple of each number in that range. that is [n/i]. so each number i in {1,...,n} appears [n/i] times. what remains for counting the number of them is summing this for all i in the range and summing i*[n/i] for the sum. This code does what you want:

int main(){
int n;
scanf("%d",&n);

int nums=0;
int sums=0;
for (int i=1; i<n+1;i++){
    nums = nums + (n/i);
}

for (int i=1; i<n+1; i++){
    sums = sums + (i* (n/i));

}
printf("%d %d",nums, sums);
}