Java第25题：分解质因数（输出 90=2×3×3×5 形式）

题目

从标准输入读入一个大于 1 的正整数 n，将其分解为质因数乘积的形式输出（例如：90=2*3*3*5）。

输入格式：一行输入一个正整数 n。

输出格式：按 n=p1*p2*...*pk 的格式输出质因数分解结果，末尾换行。

数据范围与约定：2 ≤ n ≤ 10⁹。

思路与算法

1. 试除法原理
从最小质数 d = 2 开始试除。若 x % d == 0，则 d 必为质因子，循环除尽该因子并格式化输出，然后 d++。

2. 范围缩减到 √x
因数试除只需进行到 d * d ≤ x。循环结束后若 x > 1，则剩余的 x 本身就是一个大于 √n 的质因数，直接追加输出即可。

完整程序

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        boolean first = true;
        System.out.print(n + "=");
        long x = n;

        // 试除法只需进行到 d * d <= x
        for (long d = 2; d * d <= x; d++) {
            // 反复除尽当前质因子 d
            while (x % d == 0) {
                if (!first) {
                    System.out.print("*");
                }
                System.out.print(d);
                first = false;
                x /= d;
            }
        }

        // 若最后剩余的 x > 1，说明它本身是一个大于 √n 的质数
        if (x > 1) {
            if (!first) {
                System.out.print("*");
            }
            System.out.print(x);
        }
        System.out.println();
    }
}

运行示例

输入：

90

输出：

90=2*3*3*5