-1

有没有更短更有效的方法来查找
一个数字是否可以由两个不同的平方数的乘积形成
，例如

  • 36=4*9
  • 144=16*9

帮我一个算法或逻辑

4

4 回答 4

1

应该相当容易。把你的数字分解成素数。此处提供了各种语言的算法和实现。

一旦你得到了你的主要因素，那就很容易了。浏览它们并查看是否有两对相同的数字。

例如：

36 = 2 * 2 * 3 * 3。两对（2 和 3）。有用。

144 = 2 * 2 * 2 * 2 * 3 * 3 => 两对（2*2 和 3）。有用

唯一棘手的部分是重新组合您的主要因素，以便您最终得到 X = A * A * B * B。但这也不是很难。

于 2012-12-26T13:41:58.857 回答
0

我建议你考虑以下几点：

如果一个数是两个不同平方数的乘积，那么它的形式为 n，其中对于某些值 a 和 b，n = a^2 * b^2。但是，我们知道 a^2 * b^2 = (a*b)^2 （您可以在上面的两个示例中自己检查一下）。因此，要知道一个数是否是两个平方的和，该数本身必须是一个平方数。

然后剩下的就是计算出它是两个不同平方数的乘积——这可以简单地通过以下方式完成：

如果 n = a^2 * b^2，那么对于 a <> b，n 不能等于 a^4。如果n = a^4 那么a^2 * b^2 = a^4，这又意味着b^2 = a^2，这最终意味着b = a或-a（你不说你是否计算一个值，对于这个测试来说，它是负数作为“不同的”）。

于 2012-12-26T13:51:04.163 回答
0

这个怎么样？

package Math;
public class NearestNumber {
    public static void main(String[] args) {

        int myNumber = 144;
        int min = (int) Math.sqrt(myNumber);
        int i, j, counter = 0;

        for (i=2;i<min;i++) {
            for (j=i+1;j<=min;j++) {
                if (myNumber == (i*i*j*j)) {
                    System.out.println("Possible combination are " + (i*i) + " and " + (j*j));
                    counter++;
                }
            }
        }
        if (counter==0) {
            System.out.println("No possible combination found!!!");
        }
    }
}

注意：这是打印所有可能的组合，而不是最接近的组合。我相信首先是最接近的......

上面的输出是

Possible combination are 4 and 36
Possible combination are 9 and 16

演示

于 2012-12-26T14:21:39.620 回答
0

你问的逻辑，所以这里。实施很简单。

获取数字并提取其平方根。如果它不是整数，则没有数字 A 使得 A*A = N，因此不可能有两个数字使得 B*C = A 并且你停在那里。

如果根 A是整数，则再次提取其根；让它的整数部分是 R。循环 2 和 R 之间的所有素数并使用它们来分解 A。每次你找到 A 的素数因子（它除以 A 没有余数），继续除以那个素数，直到你得到一个余。没有余数的除法次数就是那个素数的幂。把那个素数放在一个列表中，次数是它的幂。如果在除法时得到 1，则停止；如果你想出一个大于 R 的数字，你将它添加到列表中并退出循环。

最后，您将有一个列表，例如 [ 3, 3, 5, 5, 5, 7 ]。

如果你的集合只有一个成员，那么问题就没有解决方案。您可以快速检查这一点，因为当您计算 R 时，您会看到它是整数。如果它也是素数，则没有小于 R 的除数，您的集合将是 [ R ]，它不能被划分为两个非空集合。

在您的示例中，您将拥有：

144 -- root is 12
Root of 12 is 3.4, so you need only check from 2 to 3 to fill [ ]
2 divides 12 and you get 6: [ 2 ]
2 divides 6 and you get 3 [ 2 2 ]
2 does not divide 3
3 divides 3 and you get 1 [ 2 2 3 ], so exit.
Factors of 12: [ 2, 2, 3 ]

现在，字典的每个2 分区代表一对合适的数字。例如，您可以有： [ [ 3 2 ], [ 2 ] ] 表示 2^2 和 (2*3)^2 是合适的候选者，或 [ [ 2 2 ] [ 3 ] ] 表示 (2 *2)^2 和 3^2 是合适的候选人。

使用包含前 1,000 个素数的表格，您可以有效地检查多达近 5000 亿个数字；即使您可能需要 BigNum 库（libgmp、NumPy、...）来实现。

于 2012-12-26T18:35:10.263 回答