华为机试打卡 HJ6 质数因子

要机试了,华孝子求捞,功德++

描述

功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 ) 

数据范围: 1≤n≤2×109+14 

输入描述:

输入一个整数

输出描述:

按照从小到大的顺序输出它的所有质数的因子,以空格隔开。

示例1

输入:

180

输出:

2 2 3 3 5

分析

还是只会用试除法,结果提交发现超时了,虽然做的过程中尝试了用sqrt的边界,但没有单独处理另一侧导致越界

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> res = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        while (n != 1) {
            for (int i = 2; i <= n; i++) {
                if (n % i == 0) {
                    res.add(i);
                    n /= i;
                    break;
                }
            }

        }
        for (int i : res) {
            System.out.print(i+" ");
        }
    }
}

实际上直接外层for循环扫描一遍,内部用while把满足的答案(可重复)一网打尽

这样处理完后再检查是否有sqrt的对侧,此时一定是质数,并且大于之前的元素

由于for循环的顺序数组本身就是递增趋势的,可以不用排序直接输出

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> res = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            while (n % i == 0) {
                res.add(i);
                n /= i;
            }
        }
        if (n != 1) res.add(n);
        for (int i : res) {
            System.out.print(i+" ");
        }
    }
}

上一篇:MySQL两表联查之分组成绩第几问题


下一篇:前端三剑客 —— HTML (下)