质因数分解_java

什么是质因数？

        说的通俗一点就是，这个数既是因数，又是质数。但是1不是质因数(不是质数)。然后比如12=2*2*3，里边的2，3都是质数，并且也是12的因数，所以2、3就是12的质因数。

        因为本人很菜，我也不知道这个质因数在哪类题里会用到，暂时只把分解质因数的代码给搞明白了，代码如下。

        我们先来看一下具体的质因数分解的流程。

        我们的目标是把一个数分解成若干个质数相乘的形式。

步骤1：从最小的质数2开始试除

为什么从2开始？
        因为2是最小的质数，从小到大试除可以确保找到的因数都是质数。

步骤2：如果能整除，就记录这个质数，并继续用2除

        如果能被2整除，就记录"2"，并把原数除以2，继续用2试除，直到不能整除为止。

        比如分解12，

                首先是12÷2=6，然后我们把2记录一下，他是一个质因数，就是while中的k；

                然后再用2除，6÷2=3，能整除，再记录一下2；

                再用2除，3÷2不能整除，所以我们就停止用2除。

                现在得到12的质因数是2，2；

步骤3：如果不能整除，就试下一个数（3, 5, 7...）

        你看上边我们到3÷2的时候就不能整除了，所以就停止用2除，采用下一个数除，也就是3。

        然后我们刚刚停止的时候，是在3÷2停止的，然后我们现在就用3÷3，发现可以整除，好的，我们记录一下，然后像第2步一样，这时候就继续用3除，以此类推......即如果当前数不能整除，就换更大的质数试除（比如3、5、7...）。

        然后现在又得到了一个12的质因数就是3。

        综上，12的质因数就是2 2 3。

为什么不会是4，6，8，9，....呢？？？

        前提这个数我觉得不能是质数，如果num本身就是质数的话，他是会除以4，6，8这些的。

        但是如果你是个合数，你想想，如果你想要能够被4整除，你是不是这个num里得有4这个因数，或者含有4的整数倍的因数，但是你最开始一直在尝试用2这个质数去缩减num呀，所以当num%2 != 0的时候，说明里边含2这个因数的数都已经被消耗没了，4就是2*2，除两次就消耗没了，6除一次2一次3，也消耗没了，所以不可能再会被4，6，8，9这些数尝试的机会。

终止条件

从代码中理解是num <= k时，但是这里又有两种可能：

        num == k：

                说明 k 本身就是最后一个质因数，比如 5 的质因数就是它本身，你把5带入num中时，最开始5 > 2，进入while，然后5 % 2 != 0，进入else里边，2 + 1 = 3；然后5 > 3，但是5%3!=0，进入else里边，3 + 1 = 4；然后5 > 4，但是5%4 != 0，进入else里边，4 + 1 = 5；然后5 = 5，不满足while条件，出了while就把k打印，sum ++;

                这种情况我觉得num本身可能就是个质数。

        num < k:

                        这种情况实际上是不会发生的，因为你如果到了num < k这个地步，实际上你肯定也经历了num == k的这个过程，要不然你的num怎么会变小呢。既然你都经历过num == k了，说明小于等于num的数都被除过了，你再尝试大于num的数又有什么意义呢。比如17你都用17除过了，你再用17÷18其实没什么用了。所以当num==k的时候，这时的k其实就是最后一个质因数了，没有必要再往后求。

代码中可能会产生的疑惑

        为什么while循环的外侧也要打印k，也要进行sum ++;

        这是因为此时的k它是最后一个质因数，就是17的那种情况，在while里边还没来得及去记录，所以循环出来的时候要补上一个k的打印，同时质因数的个数也随之加1。

import java.util.Scanner;
public class Main {public static void main(String[] args) {int sum = 0;   // num要分解的数      sum质因数的个数Scanner sc = new Scanner(System.in);int num = sc.nextInt();int k = 2;while (num > k) {if (num % k == 0) {    // 相当于步骤2System.out.println(k);sum ++;num /= k;}else {    // 相当于步骤3k ++;}}System.out.println(k);sum ++;     // 因为while循环中，没来得及记录这个k，也没来得及更新sumSystem.out.println("质因数个数：" + sum);}
}