蓝桥杯基础练习VIP-分解质因数 （Java代码）

解题思路:
    根据公式f(n) = k * f(n / k)建立递归，采用记忆化递归减少重复计算




注意事项:
    理解递归公式，debug了半天才发现问题所在




参考代码:

import java.util.Scanner;

/**
 * @author Alex
 * @date 2018/2/24
 */
public class Basic_16 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int begin, end;
        begin = input.nextInt();
        end = input.nextInt();
        items = new String[end + 1];
        fun(begin, end);
    }

    private static void fun(int begin, int end) {
        for (int i = begin; i <= end; i++) {
            System.out.print(i + "=");
            builder = new StringBuilder();
            decomposition(i);
            System.out.println(builder.toString());
        }
    }

    //记忆化递归
    private static String[] items;
    private static StringBuilder builder;

    private static void decomposition(int n) {
        if (items[n] != null) {
            builder.append(items[n]);
        }
        //找到第一个能够分解的素数就停止循环
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                builder.append(i + "*");
                decomposition(n / i);
                return ;
            }
        }
        builder.append(n);
        return ;
    }

}