将一个正整数变成小于它的正整两个数相乘?

Question

怎么将一个正整数变成小于它的正整两个数相乘

比如 6 = 3*2
15 = 5*3

Answer 1

若只是求得两个整数，没有其他条件，那可以简单点。

前提：排除 1 和质数。质数并不存在对应的结果。

暴力枚举，设目标数字为 n，搜索 [2, n / 2] 范围即可。

放一段简单的实现，以 C 为例：

void getInt(int target) {
    for (int i = 2; i <= target / 2; ++i) {
        if (target % i == 0) {
            printf("%d * %d = %d\n", i, target / i, target);
        }
    }
}

Answer 2

不就是找质因子，然后再做质因子的组合吗？

找质因数，下面是一个 C# 代码示例：

IEnumerable<int> GetFactors(int n) {
    int v = n;
    while (v >= 2) {
        WriteLine($"v = {v}");
        int end = v / 2;
        int i;
        for (i = 2; i <= end; i++) {
            if (v % i == 0) {
                yield return i;
                v = v / i;
                break;
            }
        }
        if (i > end) { 
            yield return v;
            break;
        }
    }
}

调用如：GetFactors(180).ToArray() 可得到质因子数组。

上面这个函数调用之后加如果是一个质数，上面这段代码会返回一个仅包含这本身的 Enumerable。

拿到数组之后（只要元素个数大于 1），只需要随机截断，前后两部分相乘都是要找的数。

Answer 3

你的问题可以算是“质因数分解”，虽然并不要求解一定是质数。参考前面的链接可以了解一些因数分解相关的优化算法。