数论因子计算与数字重组算法解析

1. 问题1：奇妙的比值——因子和与数的比值计算

1.1 问题分析与数学原理

这个问题要求我们计算一个数的所有因子之和与该数本身的比值。从数学角度来看，这涉及到数论中的因子函数σ(n)，它表示n的所有正因子之和。题目要求的比值实际上就是σ(n)/n。

在数论中，这个比值被称为"丰度指数"(abundance index)，它可以用来判断一个数是亏数、完美数还是盈数：

• 当σ(n)/n < 2时，n是亏数
• 当σ(n)/n = 2时，n是完美数(如6)
• 当σ(n)/n > 2时，n是盈数

1.2 算法实现与优化

原始代码使用了遍历到n/2的方法来寻找因子，这是一个常见的优化手段，因为大于n/2的数不可能是n的因子(除了n本身)。不过我们可以进一步优化：

1. 更高效的因子查找算法：只需要遍历到√n即可，因为因子是成对出现的。例如对于n=36：

   • 1和36
   • 2和18
   • 3和12
   • 4和9
   • 6和6（特殊情况，只加一次）

2. 浮点数处理注意事项：正如总结中指出的，必须确保使用浮点数运算，否则整数除法会丢失精度。在C语言中，有两种处理方式：

   • 使用浮点变量存储和：double sum = 0;
   • 或者在除法时强制转换：(double)sum / n

优化后的算法实现：

c复制#include <stdio.h>
#include <math.h>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        double sum = 0;
        int sqrt_n = sqrt(n);
        for (int i = 1; i <= sqrt_n; i++) {
            if (n % i == 0) {
                sum += i;
                if (i != n / i) {  // 避免重复加平方根
                    sum += n / i;
                }
            }
        }
        printf