6.质数因子

raylan.chen大约 2 分钟

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int input = in.nextInt();
            List<Integer> res = isAnswer(input);
            for (int o : res) {
                System.out.print(o + " ");
            }
        }
    }

    public static List<Integer> isAnswer(int input) {
        if (input == 0) return new ArrayList<Integer>(0);
        // 合数可被质数整除
        int[] prime = new int[]{2, 3, 5, 7};
        List<Integer> res = new ArrayList<>();
        // 循环控制
        boolean flag = true;
        while (flag) {
            flag = false;
            // 遍历质数数组
            for (int i : prime) {
                // 可由某一质数相乘得出
                if (input % i == 0) {
                    flag = true;
                    input /= i;
                    res.add(i);
                    break;
                }
            }
        }
        // 最后一个质因子无法被质数整除
        if (input > 1) res.add(input);
        return res;
    }
}

遇到输入：93938

预期输出：2 13 3613

实际输出：2 46969

改进

参考 Java 优化最坏时间线性复杂度代码_牛客博客，改进代码

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int input = in.nextInt();
            boolean flag = true;
            while (flag) {
                flag = false;
                for (int i = 2; i <= Math.sqrt(input); i++) {
                    if (input % i == 0) {
                        System.out.print(i + " ");
                        input /= i;
                        flag = true;
                        break;
                    }
                }
            }
            System.out.println(input == 1 ? "" : input);
        }
    }
}

参考将一个正整数分解质因数 - 楼兰胡杨 - 博客园，可继续改进

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int input = in.nextInt();
            // 合数可由质数相乘得出，input 若能被4整除，则其也能被2整除
            for (int i = 2; i <= Math.sqrt(input); ) {
                if (input % i == 0) {
                    System.out.print(i + " ");
                    input /= i;
                } else {
                    i++;
                }
            }
            System.out.println(input == 1 ? "" : input);
        }
    }
}

6.质数因子

6.质数因子

参考链接

个人尝试（❌错误）

改进