欺骗性的简单？给定一个整数，找到恰好能够整除它的最接近的整数集合？

Question

给定一个正整数对象数量，比如小盒子，我想在桌子上整齐地摆放它们，形成一个漂亮的二维块，可能是矩形，也可能不是，但不是任何老旧的矩形，而是尽可能接近正方形的矩形。

为此，我需要两个整数，这两个整数可以将对象的整数分成最接近彼此的两个数字。

例如：

假设我有12个对象。我可以把它们排列成(12 x 1)或(1 x 12)或(6 x 2)或(2 x 6)或(3 x 4)或(4 x 3)。

我希望它们是(4 x 3)，甚至是(3 x 4)，但假设最大值首先出现，因为这是最大的一对可以将数字分成最接近的数字。

给定某个正整数x，哪种算法可以返回(y, z)？其中；

((y * z) = x) AND (y > z) AND (abs(y - z) is a minimum)

当没有解决方案时，我可以通过增加整数数量来搜索解决方案，从我实际拥有的对象数量开始，以找到附近的解决方案，然后将我的对象安装在该解决方案中，留下间隙。

但是...现在让我们加快速度！

如果我现在将其扩展到三维，而不是在平面上，并且我想要在三维空间中制作一个漂亮的整齐立方体对象块，该块具有最接近彼此的三个数字，这些数字可以被分成整数对象数量，以便从该对象数量中形成最紧凑，紧密包装的3D结构？

例如：

假设我有12个对象。我可以将它们排列为(12 x 1 x 1)或(1 x 12 x 1)或(1 x 1 x 12)或(2 x 2 x 3)或(2 x 3 x 2)或(3 x 2 x 2)...

在这里，我接受它们作为紧凑的(3 x 2 x 2)对象块。

首先，不是数学家，这种因素问题叫什么名字？其次，是否有一种算法可以为任何正整数执行此操作并建议无解时？

我知道它始于将整数数因式分解，但然后...

额外加分...是否还有一种方法可以进行四维解决方案？N维？

我正在尝试编写C++算法，但这是我遇到的一个整数数学问题。

谢谢。

- David H Parry

---

那么，您已经能够将数字分解为所需数量的因数，现在只需要一种有效的方法来在可能的维度之间进行选择？ - beaker

我正在使用标准的方法来查找因子，但是如果（x％2 == 0），那么这已经给了我所有偶数因子，所以步长为2不是更好吗？如果我只需要测试“奇数”数字，那么这会至少减少一半要测试的整数数量吧？ - David H Parry

@beaker 我也这么认为。是否有因数和因式分解以及因数集的标准库？我在想这种“最接近的因数”是否在数学上有一个名称。 - David H Parry

一旦你有了这些因素，你只需要最小化对角线的长度。对于三维空间，最小化 x^3 + y^3 + z^3。 - beaker

Answer 1

您想将整数n分解为k个因子，以最小化所有k_i之间的欧几里得距离总和。只要0 < k且0 < n，就始终存在解决方案。例如，考虑n=任何质数：解决方案为{n}+ {重复1k-1次的1}。

一种递归伪代码方法：

list<int> reduce(int n, int k, list<int> factors)
  // validity checks for 0 < k, 0 < n omitted
  // if there's only one factor left, we know what it is
  if(k == 1) 
    factors.add(n)
    return factors
  // we know all the remaining factors because n can't be reduced further
  if(n is prime || n == 1)
    factors.add(n)
    return reduce(1, k - 1, factors)
  // take the k-th root of n, rounded up
  int r = ceiling(root(n, k))
  // if there's an exact root here, we're done; remaining factor distance = 0
  if(n % r == 0)
    do k times
      factors.add(r)
    return factors
  // otherwise find the next largest remaining factor
  while(n % r != 0)
    r -= 1
  factors.add(r)
  return reduce(n / r, k - 1, factors)

这段代码的目的是清晰易懂而非优化。

从概念上来说，您正在尝试通过垂直于一个点延伸所有k个因子来最小化对角线测量。如果k=2，则通过将k₀与k₁成直角形成的直角三角形的斜边长度进行最小化。如果k=3，则通过使所有三个因子正交（即形成三维笛卡尔图的X-Y-Z轴）形成的三角形面积进行最小化。如果k=4，则通过最小化四面体固体的体积来实现；等等。为了迭代地构建此形状，上述算法使用k次方根来限制要添加的新维度的大小。

如果您希望结果排序，那么只需对返回的列表进行排序即可。假设n>>k，因此排序的k log k成本与因式分解的成本相比微不足道。或者，如果您很懒，可以使用自排序数据结构作为返回类型。

以下是一些示例：

n = 12，k = 3

• r = 3（12的立方根向上取整）
• 12％3 == 0; 3是一个因数
• 递归; n = 4，k = 2
• r = 2（4的平方根）
• 4％2 == 0; 将2添加到因子2次
• 结果：{3，2，2}

n = 32，k = 3

• r = 4（32的立方根向上取整）
• 32％4 == 0; 4是一个因数
• 递归; n = 8，k = 2
• r = 3（8的平方根向上取整）
• 8％3！= 0; r = 2
• 8％2 == 0; 2是一个因数
• 递归; n = 2，k = 1
• k == 1; 2是一个因数
• 结果：{4，2，2}

n = 25, k = 4

• r = 2（将25开平方向上取整）
• 25 % 2 != 0; r = 1
• 25 % 1 == 0; 1是因子
• 递归；n = 25，k = 3
• r = 3（将25开立方向上取整）
• 25 % 3 != 0; r = 2
• 25 % 2 != 0; r = 1
• 25 % 1 == 0; 1是因子
• 递归；n = 25，k = 2
• r = 5（将25开方）
• 25 % 5 == 0; 将5添加到因数中2次
• 结果：{1, 1, 5, 5}

更多结果：

• n = 88，k = 3 -> {4，2，11}
• n = 66，k = 5 -> {2，1，3，11，1}
• n = 14，k = 3 -> {2，7，1}
• n = 15，k = 3 -> {3，5，1}
• n = 18，k = 2 -> {3，6}
• n = 39，k = 3 -> {3，13，1}
• n = 49，k = 3 -> {1，7，7}

- Esoteric Screen Name