Java题目解析——分解因数

短命女 2023-09-30 23:02 8阅读 0赞

题目描述：

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

输入描述：

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

输出描述：

> 对应每组数据，以“a = a1 \* a2 \* a3...”的形式输出因式分解后的结果。

示例

> 输入：10
> 
> 18
> 
> 输出：10 = 2 \* 5
> 
> 18 = 2 \* 3 \* 3

**题目解析：**

> 本题可以通过循环遍历的方式找因数，从2开始，如果此时的数是因数，因为题目是分解为最简的因数，即因数都不能再分解（因数为素数），那么再建立一个内循环，判断除了这个因数后，是否还能找到这个因数，直到最后变为1结束输出；或者不满足因数要求退出，继续遍历。直到外循环也遍历完后，判断此时的数是否为1，不是1说明这个数也是因数，输出；是1说明所有因数已经输出，不需要再输出了。
> 
> 需要注意的是，循环遍历只需要遍历数字n的开方即可，因为比n的开方大的数肯定是前面因数的倍数，因数是一样的。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while(scanner.hasNextInt()){
                int n = scanner.nextInt();
                System.out.print(n + " = ");
                for (int i = 2; i <= Math.sqrt(n); i++) {
                    if(n % i == 0){
                        while(n % i == 0){
                            int t = n / i;
                            if(t == 1){
                                System.out.println(i);
                            }else{
                                System.out.print(i + " * ");
                            }
                            n /= i;
                        }
                    }
                }
                if(n != 1){
                System.out.println(n);
                }
            }
        }
    }

如有建议或想法，欢迎一起学习讨论~