找一个数的最接近因数

Question

我正在尝试自动查找一个数字到另一个数字的最接近因数；

例子：

700的最接近30的因数是28（30不能整除700，但是28可以）。

一个显而易见的解决方案是获取700的所有因数并进行简单的距离计算以找到最接近30的因数，但这似乎效率低下。

另一种解决方案是找到所有基本质因数，例如：

private List<Integer> getPrimeFactors(int upTo) {
    List<Integer> result = new ArrayList<>();
    for (int i = 2; i <= upTo; i++) {
        if (upTo % i == 0) {
            result.add(i);
        }
    }
    return result;
}

将每个数字相乘以得到所有组合，从而找到最接近的组合。

我正在尝试编写自动化程序。是否有更好的解决方案？

- Cobbles

---

这是一个数学问题，如果您有编程问题，请说明。 - No Idea For Name

不断递减你的数字（30），直到找到一个使 input % value == 0 的数字。虽然我不知道这是否更有效 :-) - Robby Cornelissen

@RobbyCornelissen 不要忘记递增。 - kai

@RobbyCornelissen nearest 是最近的，上面或下面。 - Cobbles

在这种情况下：增加和减少。现在肯定听起来不太有效率 :) - Robby Cornelissen

Answer 1

你不需要计算所有因数，但是你可以从这个数字双向查找，找到最接近给定数字的因数。

伪代码如下：

n= given number(dividend);
x= second number( whose closest number is required)
i=0;
if(n%x==0) print x;
else
while(true){
   if(n%(x-i)==0){
      print x-i
      break 
   }
   else if(n%(x+i)==0){
     print x+i;    
       break 
   }
   else i=i+1
}

- Aayush Rathore

---

你的（伪）代码对于 n=19 和 x=3 会发生什么？ - CiaPan

@CiaPan：在我看来，这段代码似乎会打印出“1”。 - Zéychin

是的，它会打印1，因为它是最接近满足给定条件的数字。 - Aayush Rathore

啊，是的，你们都对。我一定是看错了代码……顺便说一句，第一个if..else不必要，在第一个while迭代中会重复执行相同的测试（两次），因为此时i==0。 - CiaPan

Answer 2

我有一个小的静态方法来包装我的解决方案：

/**
* @param target the number you want the factor to be close to
* @param number the number you want the result to be a factor of
*/
private static int getClosestFactor(int target, int number) {
    for (int i = 0; i < number; i++) {
        if (number % (target + i) == 0) {
            return target + i;
        } else if (number % (target - i) == 0) {
            return target - i;
        }
    }
    return number;
}

- Cobbles

---

什么是number，什么是max？这似乎完全错误。 - Udo

@Udo 能否详细说明一下？Number 是您想要因子接近的数字，而 max 是您正在除以的数字。 - Cobbles

将“number”重命名为“target”，将“max”重命名为“number”，并且不要忘记检查“number％target == 0”。 - Teepeemm

好的，一般来说这个代码是可以工作的，但是在第一次返回时你肯定是想要 return target + i。并且它在处理一些极端值时会出现问题。如果 target = 0，它将会崩溃。如果 target < -2 * number，你将会得到 number 作为结果，但是实际上应该是 1（如果只需要正因子）。 - Udo

Answer 3

    package dummy;

    public class test {

        public static void main(String[] args) {
            int factorOff = 700;
            int factorFrom = 30;
            for (int i = 2; i < factorOff; i++) {
                if (factorOff % (factorFrom + i) == 0) {
                    System.out.println(factorFrom + i);
                    i = factorOff;
                } else if (factorFrom - i > 1 && factorOff % (factorFrom - i) == 0) {
                    System.out.println(factorFrom - i);
                    i = factorOff;
                }
            }
        }
    }

- Fanish

Answer 4

这应该是一个快速解决方案：

public static int findClosestFactor(int number, int closeTo) {
    int result = 1;
    int currentDist = closeTo - 1;
    // stop conditions for comparison
    boolean compareSmallFactor = true;
    boolean compareLargeFactor = true;
    for (int factor1 = (int) Math.sqrt(number); factor1 > 0; factor1--) {
        if (number % factor1 == 0) {
            if (compareSmallFactor) {
                int dist1 = Math.abs(closeTo - factor1);
                if (dist1 < currentDist) {
                    result = factor1;
                    currentDist = dist1;
                }
                // factor 1 is getting always smaller
                // so you need not compare next time, if go away from target (smaller than target)
                if (factor1 <= closeTo) {
                    compareSmallFactor = false;
                }
            }

            if (compareLargeFactor) {
                int factor2 = number / factor1;
                int dist2 = Math.abs(closeTo - factor2);
                if (dist2 < currentDist) {
                    result = factor2;
                    currentDist = dist2;
                }
                // factor 2 is getting always larger
                // so you need not compare next time, if go away from target (larger than target)
                if (factor2 >= closeTo) {
                    compareLargeFactor = false;
                }
            }

            // if both factors go away from target, you can cancel
            if (!compareSmallFactor && !compareLargeFactor) {
                break;
            }
        }
    }
    return result;
}

- Udo

Answer 5

你可以将数字进行因式分解，然后使用幂集生成器（对于多重集[1]）来搜索最接近最大值但不超过的因子组。

幂集生成器可以修改为防止进一步迭代下超过所需值的分支（分支限界）。例如：如果因子是（2,5,7,13,19）。数字是80，而你有2 * 5 * 7 = 70。2 * 5 * 7 * 13 = 910。没有必要检查2 * 5 * 7 * 19，因为它显然会超过最大值。

[1] 将因式分解视为多重集是一个好主意。例如，在700的情况下，((2,2),(5,2),(7,1))。你可以将其视为(2,2,5,5,7)，但这样做会做额外的工作，因为没有必要找到2 * 5 = 10超过一次，但如果它不被视为多重集，则会发生这种情况。

- Nuclearman