华为OD机考题(HJ6 质数因子)

 前言

经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。

描述

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

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

输入描述：

输入一个整数

输出描述：

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

示例1

输入：

180

输出：

2 2 3 3 5

实现原理与步骤

1.从最小的质数 2 开始，检查是否能整除该数。

2.如果能整除，则将该质数作为因子，并继续用商进行下一步检查。

3.重复上述过程直到商为 1。

实现代码

import java.util.*;  // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         // 注意 hasNext 和 hasNextLine 的区别         int input=in.nextInt();         List<Integer> factors = new ArrayList<>();         while(input%2==0){             input/=2;             factors.add(2);         }         for(int i=3;i<=Math.sqrt(input);i+=2){             while(input%i==0){                 input/=i;                 factors.add(i);             }         }         if(input>2){             factors.add(input);         }         for(int i=0;i<factors.size();i++){             System.out.print(factors.get(i)+" ");         }      } }

1.QA: