Java实现查找满足指定乘积与和的因数对（三项式因式分解场景）

需求说明 #

开发计算器工具时需要实现因数匹配逻辑：找到两个整数，二者乘积为指定值、和为另一指定值，用于三项式因式分解场景。例如对$x^2 +9x +20$，符合要求的因数对是4和5，满足4*5=20、4+5=9，最终分解结果为$(x+4)(x+5)$。
程序采用主类调用功能函数的架构，目前已经完成基础的因数获取框架，待补充匹配判断逻辑，现有代码如下：

public static void MA() {
     int sum = 0;
     int product = 0;
     ArrayList<Integer> Factors = new ArrayList<Integer>();

     
     
     System.out.println("Enter the sum of the number");
     sum = sc.nextInt();
     System.out.println("Enter the number it should multiply to");
     product = sc.nextInt();

if(product < 0){
  for(int i = product; i <= Math.abs(product); ++i) {

      // skips the iteration for i = 0
      if(i == 0) {
        continue;
      }
      else {
        if (product % i == 0) {
          Factors.add(i);
        }
}
    }
  }
  else{
    for (int i = 1; i <= product; ++i) {
  
      // if number is divided by i
      // i is the factor
      if (product % i == 0) {
        Factors.add(i);
      }
    }
  }  

  System.out.println(Factors);
   }

现存问题 #

• 缺少因数对匹配逻辑，无法从已获取的因数列表中筛选出和为目标值的配对
• 正数乘积的因数收集逻辑存在缺陷：仅收集了正因数，漏掉了负因数场景，无法适配和为负数、乘积为正数的三项式分解（比如$x^2-9x+20$对应的-4、-5因数对）

实现步骤 #

1. 统一因数收集逻辑 #

不需要单独判断product正负，直接遍历从-Math.abs(product)到Math.abs(product)的所有非0整数，能整除product的就加入因数列表，同时覆盖正负因数场景，减少冗余代码。

2. 因数对匹配逻辑 #

利用因数成对出现的特性，不需要做O(n²)的两两组合判断：

• 遍历因数列表中的每个值a
• 计算配对值b = product / a（a是product的因数，必然整除，无精度问题）
• 判断a + b == sum是否成立，成立即为目标因数对
• 增加a <= b判断避免重复输出同一组因数（比如避免先后输出(4,5)和(5,4)）

修正后完整代码 #

注意需要将Scanner对象声明为类静态成员，供静态方法MA调用：

import java.util.ArrayList;
import java.util.Scanner;

public class Calculator {
    // 声明为类静态成员，供静态功能方法调用
    private static Scanner sc = new Scanner(System.in);

    public static void MA() {
        int sum = 0;
        int product = 0;
        ArrayList<Integer> factors = new ArrayList<>();

        System.out.println("Enter the sum of the number");
        sum = sc.nextInt();
        System.out.println("Enter the number it should multiply to");
        product = sc.nextInt();

        // 统一收集所有正负因数，跳过0
        int absProduct = Math.abs(product);
        for(int i = -absProduct; i <= absProduct; ++i) {
            if(i == 0) continue;
            if (product % i == 0) {
                factors.add(i);
            }
        }

        // 匹配因数对
        int factor1 = 0, factor2 = 0;
        boolean found = false;
        for (int a : factors) {
            int b = product / a;
            // 加a<=b判断避免重复匹配
            if (a + b == sum && a <= b) {
                factor1 = a;
                factor2 = b;
                found = true;
                break;
            }
        }

        // 输出结果
        if (found) {
            System.out.printf("找到符合要求的因数对：%d 和 %d%n", factor1, factor2);
            System.out.printf("三项式分解结果：(x%+d)(x%+d)%n", factor1, factor2);
        } else {
            System.out.println("不存在整数因数对满足要求，无法在整数范围内分解三项式");
        }
    }

    public static void main(String[] args) {
        // 主类调用功能函数
        MA();
    }
}

测试验证 #

输入sum=9、product=20时，输出：

找到符合要求的因数对：4 和 5
三项式分解结果：(x+4)(x+5)

输入sum=-9、product=20时，输出：

找到符合要求的因数对：-5 和 -4
三项式分解结果：(x-5)(x-4)

输入sum=1、product=-20时，输出：

找到符合要求的因数对：-4 和 5
三项式分解结果：(x-4)(x+5)

内容的提问来源于stack exchange，提问作者Kaicheng Ouyang