《分解因数》：质因数分解

目录

一、题目：

二、思路：

 三、代码：

---

 

一、题目：

分解因数      《分解因数》题目链接

        所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an。其中a1、a2、...、an均为素数。 先给出一个整数a，请输出分解后的因子。 

输入描述:
输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。

输出描述:
对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。示例1
输入
10

18
输出
10 = 2 * 5

18 = 2 * 3 * 3

二、思路：

        本题是因子分解，但是需要考虑素数的分解。即：

• 如果是素数：例如 5 = 5
• 如果是合数：例如12 = 2 * 2 * 3 

         从i = [ 2 , sqrt(a) ]循环判断，如果 i 能被 a 整除，就进入内循环。这个过程类似 《因子个数》的题。方法思路是一样的。题目链接：因子个数

具体思路在代码中。

1、题目要求的输入输出

        因为最后输出有格式要求，所以我们用 printf 格式化输出，每个输出的后面都不一样，所以用字符串进行后面的显示。

        使用 String.join()方法：返回使用指定分隔符拼接后的字符串。传入的参数有两个：分隔符（要以什么符号进行拼接）、需要拼接的字符串的数组/集合...这里使用List

2、质因数分解

         循环从 2 开始判断，注意判断的范围 i <= Math.sqrt(n)  <--等价于--> i * i <= n

如果 n = x * y，那么如果 x <= y ，那么 x 一定在 [ 2 ,  ] 中。

 三、代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** Created with IntelliJ IDEA.* Description: 质因数分解* User: WangWZ* Date: 2023-04-12* Time: 16:33*/
public class Main {//质因数分解: 分解 nprivate static ArrayList<String> func(int n) {ArrayList<String> ans = new ArrayList<>();//循环判断是否是 n的因子//i <= Math.sqrt(n) 也可以写成 i * i <= nfor(int i = 2; i <= Math.sqrt(n);i++) {//因为题目中，一个因子可以乘积多次，所以用 while循环//每循环一次更新 n 的值，再继续找更新后的 n的值的因子while(n % i == 0) {//此时 i 是 n 的一个因子，所以将 i 加入ans//ans 中存储的是String类型的，而 i是 int类型，所以要进行类型转换//使用String.valueOf(i)ans.add(String.valueOf(i));if(n % 1 == 0) {n = n / i;}}}//判断 n 的值//如果 n != 1,说明此时 n 是素数，其也是传入参数 n 的一个因子//如果 n == 1,说明上面的循环已经把 传入参数 n的全部因子找到了if(n != 1) {ans.add(String.valueOf(n));}//循环结束,返回ansreturn ans;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()) {//输入是数字int n = scanner.nextInt();//因为最后输出有格式要求，所以我们用 printf格式化输出//每个输出的后面都不一样，所以用字符串进行后面的显示//使用 String.join()方法：返回使用指定分隔符拼接后的字符串//传入的参数有两个：分隔符（要以什么符号进行拼接）、需要拼接的字符串的数组/集合...//这里使用ListList<String> list = func(n);System.out.printf("%d = %s\n",n,String.join(" * ",list));}}
}