更好的算法来找到平方除 K 的最大数：

Question

给定一个数字 K，它是两个不同数字 (A,B) 的乘积，找到最大数字 (<=A & <=B) who's square divides the K .

)

例如：K = 54 (6*9) 。这两个数字都可用，即 6 和 9。

我的方法相当非常简单或微不足道。

1. 取两者中最小的一个（在本例中为 6）。可以说 A
2. 将数字平方并除以 K，如果完全除法，就是数字。
3. 否则A = A-1，直到A =1。

对于给定的示例，3*3 = 9 除 K，因此答案为 3。

寻找比平凡解决方案更好的算法。

注意： 测试用例有 1000 个，因此需要最好的方法。

Answer 1

我相信其他人会想出一个涉及模运算的好答案。 这是一个幼稚的方法...

每个因子本身都可以被分解（尽管这可能是一个昂贵的操作）。

给定这些因素，您就可以寻找重复因素组。

例如，使用您的示例：

9 的质因数：3, 3

6 的质因数：2, 3

所有质因数：2, 3, 3, 3

有两个 3，所以你就有了答案（3 的平方除以 54）。

第二个例子 36 x 9 = 324

36 的质因数：2,2,3,3

9 的质因数：3, 3

所有质因数：2, 2, 3, 3, 3, 3

所以有两个 2 和四个 3，这意味着 2x3x3 是重复的。 2x3x3 = 18，所以 18 的平方除以 324。

编辑：python原型

import math

def factors(num, dict):
    """ This finds the factors of a number recursively.
        It is not the most efficient algorithm, and I 
        have not tested it a lot.  You should probably
        use another one. dict is a dictionary which looks
        like {factor: occurrences, factor: occurrences, ...}
        It must contain at least {2: 0} but need not have 
        any other pre-populated elements.  Factors will be added
        to this dictionary as they are found.
    """

    while (num % 2 == 0):
        num /= 2
        dict[2] += 1
    i = 3
    found = False
    while (not found and (i <= int(math.sqrt(num)))):
        if (num % i == 0):
            found = True
            factors(i, dict)
            factors(num / i, dict)
        else:
            i += 2
    if (not found):
        if (num in dict.keys()):
            dict[num] += 1
        else:
            dict[num] = 1
    return 0


#MAIN ROUTINE IS HERE

n1 = 37 # first number (6 in your example)
n2 = 41 # second number (9 in your example)
dict = {2: 0} # initialise factors (start with "no factors of 2")
factors(n1, dict) # find the factors of f1 and add them to the list
factors(n2, dict) # find the factors of f2 and add them to the list
sqfac = 1
# now find all factors repeated twice and multiply them together
for k in dict.keys():
    dict[k] /= 2
    sqfac *= k ** dict[k]
# here is the result
print(sqfac)

Answer 2

C++答案

int func(int i, j)
{ 
    int k = 54
    float result = pow(i, 2)/k
    if (static_cast<int>(result)) == result) 
    {
        if(i < j)
        {
            func(j, i);
        }
        else
        {
            cout << "Number is correct: " << i << endl;
        }
    }
    else
    {
        cout << "Number is wrong" << endl;
        func(j, i)

    }
 }

说明：

首先递归，然后测试结果是否为正整数，如果是，然后检查另一个倍数是否小于或大于，如果更大的递归函数尝试另一个倍数，如果不是，则它是正确的。然后，如果结果不是正整数，则打印 Number 错误，并执行另一个递归函数来测试 j。

Answer 3

如果我的问题正确，我会看到你有一个长度=A，宽度=B，面积=K的矩形 你想把它转换成正方形并失去尽可能小的面积

如果是这样的话。因此，您的算法的问题不在于多次迭代直到获得输出的成本。 相反，问题在于您的算法很大程度上取决于输入矩形的长度 A 和宽度 B。 虽然它应该只取决于面积 K

例如：

• 假设A=1，B=25
• 则 K=25（矩形区域）
• 您的算法将取最小值，即 A 并接受它作为答案 迭代速度非常快，但会导致错误的答案，因为它会产生面积为 1 的正方形并浪费剩余的 24（无论 cm 或米）
• 虽然这里的正确答案应该是 5。但你的算法永远无法达到这个值

因此，在我的解决方案中，我假设单个输入 K

我的想法如下

• x = sqrt(K)
• if(x is int) .. x 是答案
• else 从 x-1 循环到 1, x--
• 如果 K/x^2 是 int，则 x 就是答案

这可能需要额外的迭代，但会保证准确的答案 另外，可能有人担心 sqrt(K) 的成本 但它只会被调用一次，以避免误导长度和宽度输入

Answer 4

如果您对 K 进行素因式分解，则可以轻松找到 K 的最大平方因数。然而，这是一个昂贵的操作，但如果您已经知道对于已知的 A 和 B，K = A*B，则 A 和 B 的因式分解然后可以很容易地组合起来得到 K 的素因数分解。For

K = prod_{p prime | K} p_i^{e_i}

gsd(K) = prod_{p prime | K} p_i^{e_i - {e_i & 1}}

其中，当 e_i 为奇数时，{e_i & 1} 为 1，否则为零。

对于足够小的整数，例如64 位，可以通过试除法高效计算根式直至立方根，而无需了解完整的素因数分解。请参阅整数的最大无平方除数（又称根式）算法。假设你知道 A 和 B 的部首，那么

rad = radical(K) = radical(A)*radical(B) / gcd(radical(A), radical(B))

可以使用以下算法从根式有效计算 K 的最大平方除数。

function gsd(K, rad) {
  if (K <= 1) return K
  w = gcd(rad, K/rad)
  v = K
  u = 2
  while (u > 1) 
    u = gcd(v, w)
    v /= u
  x = K/(v*w*w)
  if (x == 1) return w*w
  return w*w*(gsd(x, gcd(rad, x)))