除数计数总和给出了耗时的问题

Question

我想为给定的 n 写出 1,...,n 之间所有数字的除数，然后得出它们的个数和它们的总和。例如：对于 3： 1,1,2,1,3 输出为 5、8 我尝试获取 1,n 范围内的每个 j，然后使用以下代码计算除数的数量但由于耗时，效率不高。

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

这是一个著名的问题，所以之前应该有人问过。不是得到每个数字然后找到它的除数，您可以简单地计算出该范围内每个数字的倍数有多少。

即[n/i]。所以 {1,...,n} 中的每个数字 i 出现 [n/i] 次。剩下来计算它们的数量就是将其相加范围内的所有 i 和 i*[n/i] 求和。此代码可以满足您的需求：

而不是获取每个数字然后找到它的除数，您可以简单地计算出该范围内每个数字的倍数有多少。即 [n/i]。所以 {1,...,n} 中的每个数字 i 出现 [n/i] 次。剩下来计算它们的数量就是将其相加范围内的所有 i 和 i*[n/i] 求和。此代码可以满足您的需求：

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);
}

除数计数总和给出了耗时的问题

divisors count sum gives time consuming issue

c

division