分解质因数

1. 分解质因数

给定⼀个正整数num，将这个正整数分解质因数，返回分解后的结果。

• 输入输出说明及示例输入只有⼀⾏，包含一个数字，即要被分解的数字。
• 输出为分解后的结果，且结果按照从⼩到⼤的顺序输出
• 示例：
  • 输⼊：90
  • 输出：90=233*5 注：测试用例不会出现输⼊为1的情况

1.1. 又臭又长版本

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        // List<Integer> list = new ArrayList<Integer>();
        Boolean flag  = true;
        System.out.print(n + "=");
        for(int i=2;i<=n;i++){
            if(n % i==0){
                for(int j=2;j<i;j++){
                    if(i % j==0){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    if(n / i==1){
                        System.out.print(i);
                        break;
                    }else{
                        System.out.print(i+"*");
                        n /=i;
                        i = 1;// 这个是关键,保证了同样的质因数可以被打出来
                        // System.out.print("<"+n+">");
                    }
                    
                }
                flag =true;
            }
        }
        input.close();
    }
}

1.2. 原始版本

import java.util.*;
public class Test {
    public static void main(String[] args){
        int num;
        Scanner input = new Scanner(System.in);
        num = input.nextInt();
        System.out.print(num+"=");
        int temp = num;
        for(int i=2;i<num/2;i++){
            // 判断是否是因子
            // 循环-->从而不放过相同数值的因子
            while (temp %i==0){
                Boolean flag = true;
                // 判断是否是素数--->看了后面的分析,会发现根本这个不用判断
                for(int j=2;j<i;j++){
                    if(i%j==0)
                        flag = false;
                }
                if(flag)
                    System.out.print(i);
                    // 判断是否是最后一位
                    if(temp / i !=1)
                        System.out.print("*");
                // 不仅是整除,更是分解,因而被除数每除以除数
                temp /= i;
            }
        }
 
        input.close();
    }
}

1.3. 观察版本

再看看洞察了”质数被1和自身整除”,从而融入到判断条件中之后:

 
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();  //用户输入数值
        int k=2;
        System.out.print(n + "=" );
        while(k <= n){
            // 洞察之后真的不一样啊
             if(k == n) {
                 System.out.println(n);
                 break;  // 如果质数k等于n 说明n是质数 所以分解质因数的过程结束 用break跳出while循环 输出n即可
              }
             else if( n % k == 0){
                System.out.print(k + "*");
	            n = n / k;
             }   //如果n不等于k且能被k整除 输出k的值 并用n除以k的商作为新的正整数n 继续while循环。
            else k++;  //将k这个因子判断完再不能除之后看后面k+1的可能性
        }
        input.close();
    }
}

以及无声的融入判断条件—直接限制变量范围即可

 
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n = input.nextInt(); 
        System.out.print(n +"="); 
        //当i值大于n的平方根时停止，留下最后一个质因数
        for(int i = 2;i<= Math.sqrt(n);i++){
          if(n % i==0){
            System.out.print(i+"*");
            n = n / i;
            i--; //令i自减，再次判断是否可以被整除
          }
        }
        System.out.println(n); //输出最后一个质因数
        input.close();
    }
}