算法:质数因子

一.需求描述

   如:180 = 2 * 2 * 3 * 3 * 5, 则180 的质数因子就是 2 2 3 3 5

 

二.实现思路

 

  1. 180 = 2 * 90

  2. 180 = 2 * 2 * 45

  3. 180 = 2 * 2 * 3 * 15

  4. 180 = 2 * 2 * 3 * 3 * 5

  

  由于2, 3, 5 都是质数,所以结束.

 

三.代码实现(List)

 

   1. 将 180 放入 list, 此时list:[180];

   2. 遍历list,判断180不是质数,则计算他的因子,并且取代他,此时list:[2, 90];

   3. 遍历list,判断  90不是质数,则计算他的因子,并且取代他,此时list:[2, 2, 45];

   4. 遍历list,判断  45不是质数,则计算他的因子,并且取代他,此时list:[2, 2, 3, 15];

   5. 遍历list,判断  15不是质数,则计算他的因子,并且取代他,此时list:[2, 2, 3, 3, 5];

   6. 遍历list,此时都为质数,所以循环结束,此时的list元素即为最终结果.

 

四.代码

import java.util.ArrayList;
import java.util.List;

public class Demo {

    public static void main(String[] args) {

        List<Long> data = new ArrayList<Long>();

        data.add(180L);

        task(data);

        System.out.println("最终结果:" + data);
    }

    private static void task(List<Long> data) {

        System.out.println("过程结果:" + data);
        for (int i = 0; i < data.size(); i++) {

            long num = data.get(i);
            if (isZhishu(num)) {
                continue;
            }

            for (long j = 2; j < num; j++) {
                if (num % j == 0) {
                    data.remove(i--);
                    data.add(j);
                    data.add(num / j);
                    break;
                }
            }
            System.out.println("过程结果:" + data);
        }
    }

    private static boolean isZhishu(long num) {

        long sqrt = (long) Math.sqrt(num) + 1;

        for (int i = 2; i < sqrt; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

五.结果:

 

过程结果:[180]
过程结果:[2, 90]
过程结果:[2, 2, 45]
过程结果:[2, 2, 3, 15]
过程结果:[2, 2, 3, 3, 5]
最终结果:[2, 2, 3, 3, 5]