0

我不擅长数学术语。

这个叫什么？

假设你有数字 48，你需要找到 48 的两个因数。在 48 中将是 8,6 在 72 中将是 9,8

我不想为 48 或 12,6 说 12,4

4

6 回答 6

2 
public static int[] revominuteFactors(long x) {
    int[] result = new int[2];
    for (int a = 0; a <= x; a++) {
        for (int b = 0; b <= x; b++) {
            if ((a * b) == x) {
                if (result[0] == 0 && result[1] == 0) {
                    result[0] = a;
                    result[1] = b;
                } else if (Math.abs(a - b) < Math.abs(result[0] - result[1])) {
                    result[0] = a;
                    result[1] = b;
                }
            }
        }
    }
    return result;
}

问了一位数学教授，他说它的名字与 revominute 因素有关。

于 2012-07-04T00:56:06.353 回答
1

距离最小的一对因子没有特定的名称。但是很容易计算出这是不是你想要的。（至少和一般的因式分解一样容易，但对于小数来说它是微不足道的。）

这是一种方法（当两个因素接近时，这将是最快的。）它基于费马的因式分解算法。

static int sqrRoot(int n){
    //Find largest square <= n
    int sqr = 0;

    for (int i=15; i >= 0; --i){
        int newsqr = sqr + (1<<i);
        if (newsqr * newsqr <= n) {sqr = newsqr;}
    }

    return sqr;
}

static int[] closestFactors(int n){
    if (n <= 0) {throw new IllegalArgumentException();}

    int s = sqrRoot(n);
    if (s*s == n){
        int[] ans = {s,s};
        return ans;
    }

    int a = s * s - n;      
    while(s < n){
        if (a > 0){ //may not be true on first iteration
            int sa = sqrRoot(a);
            //whole number case
            if (sa*sa == a){    //We found a factorization
                int[] ans = {s-sa, s+sa};
                return ans;
            }
        }

        //half number case
        int sa2 = sqrRoot(a+s);
        if (sa2 * (sa2+1) == a+s){
            int[] ans = {s-sa2, s+sa2+1};
            return ans;
        }

        a += s + s + 1;
        s++;
    }

    int[] ans = {1, n};
    return ans;
}
于 2012-07-04T00:47:06.870 回答
1

我不知道这个的名字。

在 Java 中，您的计算方式与在任何其他语言中相同。

  1. 对数字进行因式分解。
  2. 将一组因子划分为两个子集，以使两组乘积之间的差异最小化。蛮力应该作为第一次尝试......除非有很多因素。

请注意，在最坏的情况下，第 1 步是 NP，第 2 步（蛮力）是“仅” O(F^3)，其中F是因素的数量。

一种更暴力的方法是在适当范围内迭代成对的数字，测试它们的乘积是否是原始数字。

编码和调试留给读者作为练习:-)

于 2012-07-04T00:50:10.547 回答
1

显然，您可以找到所有因素并从列表中选择适当的因素。

作为替代方案，您可以从low = high = floor(sqrt(n)). 然后，如果low * high < n，增加high; 如果low * high > n, 减量low; 如果low * high = n，则(low, high)作为答案返回。这不是非常有效，但您可能会进行一些小的优化。

例子：

n = 325
low = 18, high = 18, low * high = 324
low = 18, high = 19, low * high = 342
low = 17, high = 19, low * high = 323
low = 17, high = 20, low * high = 340
low = 16, high = 20, low * high = 320
low = 16, high = 21, low * high = 336
low = 15, high = 21, low * high = 315
low = 15, high = 22, low * high = 330
low = 14, high = 23, low * high = 322
low = 14, high = 24, low * high = 336
low = 13, high = 24, low * high = 312
low = 13, high = 25, low * high = 325
answer: 13, 25

这很粗略，但可以替代因式分解。请注意，找到像这样的两个因子的任何有效解决方案都能够有效地分解密码学中使用的伪素数，因此您可能不会很快得到任何东西。

于 2012-07-04T00:57:59.270 回答
1

要在通常情况下进行因式分解N，一个简单的算法是从 开始p = 2并检查是否p除以N。如果不是，则设置p为下一个值（例如下一个整数或下一个素数）并重复。

在您的问题的理想情况下，这些因素将接近sqrt(N). 因此，您可以从 开始p = floor(sqrt(N))并递减p，直到找到一个除以N.

每次减少测试值都会起作用。在通常情况下，可能有数学上更聪明的方法 - 例如尝试连续的素数。如果一个数可以因式分解，那么素数就可以作为一个因式。但是在您的问题中，您并不关心素数，因此您在这里可能无法使用它们。

于 2012-07-04T01:00:26.030 回答
1

我认为这样的数字没有特定的名称。至于找到它们，最简单的方法可能是（给定一个数字 n）：

int factor1, factor 2;
for (int i = (int)(Math.sqrt(n)); i > 0; i--) {
    if (i/n == (double)i/n) {
        factor1 = i;
        factor2 = i/n;
        break;
    }
}

希望有帮助！

于 2012-07-04T01:01:43.213 回答