新华三笔试题 - 求最中间的因数

题目

时间限制： C/C++1秒，其他语言2秒

空间限制： C/C++ 262144K，其他语言 524288K

64bit IO Format: %lld

请完成最中间因数函数 MidFactor，寻找一个整数的所有因数中最中间的那个数。

举例：

• 16有5个因数，分别是1，2，4，8，16，最中间的是4
• 12有6个因数，分别是1，2，3，4，6，12.最中间的是3

long long MidFactor(long long llVal)
{
}

int main (int argc, char *argvD)
{
    long long llVal =0;
    if (argc < 2)
    {
        return 1;
    }
    llVal= (long long)atol(argv[1);
    printf("%ll", MidFactor(llVal);
    return 0;
}

[]$ ./a.out 16
4

[]$ ./a.out 12
3

示例1

输入

16

输出

4

解题思路

这个题做得挺快的，暴力解的话遍历就可以，主要需要注意遍历的边界。

首先，要找到一个数的所有因数，一下就能想到的就是从 1 开始遍历，能整除的就是其因数，代码大概是这样：

for (int i = 1; i < num; i++){
    if(num % i) {
        // i是num的因数
    }
}

然后进一步的不难发现，任意的一个因数 i 都和 num / i 对应是一组因数，也就是说上面的 if 语句内部得到了因数 i 的同时还得到了另一个与之对应的因数 num / i 。

再回到这个题里面来，这种要找中间的值的问题，往往我们会考虑把所有可能的值找出来后，再去找位于中间的那一个。但正如前面所说，因数总是一一对应的，这就意味着我们从 1 开始遍历，i 变大的同时，与之对应的 num / i 在逐渐变小，以 16 为例：

1 - 16
2 - 8
4 - 4  // 最中间的因数
8 - 2
16 - 1

i 逐渐增大，会在过了某个临界值（如上4）之后大于 num / i ，而这个临界值其实就是最中间的因数。

因此，只需要把遍历的边界设置为 i 从 1 开始且 i * i <= num 即可，初始化最中间的因数 mid 为 1 ，每新找到一个更大的因数就更新 mid 的值，当 i 越过边界跳出循环后，mid 的值即为 num 所有因数中最中间的哪一个。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求 一个数    最中间的因素
     * @param llVal long长整型 正整数
     * @return long长整型
     */
    long long MidFactor(long long llVal) {
        // write code here
        long long mid = 1;
        for (long long i = 1; i * i <= llVal; i++) {
            if (llVal % i == 0) {
                mid = i;
            }
        }
        return mid;
    }
};