题意整理。

  • 输入一个正整数。
  • 按照从小到大的顺序输出所有质因子。

方法一（循环）

1.解题思路

  • 遍历所有可能的质因子。
  • 只要当前数字可以分解，则一直分解下去，并输出过程中产生的质因子。

图解展示： alt

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        //遍历所有可能的质因子
        for(int i=2;n!=1;i++){
            while(n%i==0){
                n/=i;
                //输出质因子
                System.out.print(i+" ");
            }
        }
    }
}

3.复杂度分析

  • 时间复杂度：最坏的情况下需要遍历n-1次，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)。

方法二（缩小范围）

1.解题思路

假设一个数为n，它的平方根为q。如果n能被一个大于q的数整除，记为m（m>q），那么n也一定能被n/m整除，而n/m小于q。所有遍历质因子的时候，只需寻找[2,q]范围内的质因子即可。

其它的地方与方法一大致相同。

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        //取输入n的平方根
        long q=(long)Math.sqrt(n);
        //遍历所有可能的质数因子
        for(int i=2;i<=q;i++){
            //因为是从最小的因子开始分解质因子，所以不会存在分解出合数的情况
            while(n%i==0){
                n/=i;
                System.out.print(i+" ");
            }
        }
        //如果最后不为1，说明剩下的是一个质数，直接输出
        if(n!=1){
            System.out.print(n+" ");
        }
    }
}

3.复杂度分析

  • 时间复杂度：最坏的情况下需要遍历n−1\sqrt{n}-1次，所以时间复杂度为O(n)O(\sqrt{n})。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)。