蓝桥杯算法练习 - 分解质因数

原文: 蓝桥杯算法练习 - 分解质因数
date: 2014-11-14 12:39:04

问题描述：

求出区间[a,b]中所有整数的质因数分解。

输入格式：

输入两个整数a，b。

输出格式：

每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)

样例输入：

3 10

样例输出：

3=3
4=225=56=23
7=7
8=222
9=3310=25

提示：

先筛出所有素数，然后再分解。

数据规模和约定：

2<=a<=b<=10000

实现：

主函数Main

public class ResolvePrimeFactor {

    public static void main(String[] args) {
        System.out.println("Please input startNum endNum:");
        Scanner scanner = new Scanner(System.in);
        int start = scanner.nextInt();
        int end = scanner.nextInt();

        for (int i = start; i <= end; ++i) {
            System.out.print(i + "=");
            fun(i);
            System.out.println();
        }

    }
}

普通方式-循环

普通方式, 循环

public static void fun(int n) {
    int k = 2; // --定义一个标 k

    while (k <= n) {
        if (n % k == 0) {
            System.out.print(k);

            // 若后面还有 项, 输出"*" 后继续判断
            n = n / k;
            if (k <= n) {
                System.out.print("*");
            }
        } else {
            k++;
        }
    }
}

递归方式 一

递归方法 一: (while ..) 自己写的递归， 略繁琐

public static void recfun(int n) {
    int k = 2;
    while (k <= n) {
        if (n % k == 0) {
            System.out.print(k);
            if (k <= n / k) {
                System.out.print("*");
                recfun(n / k);
                return;
            }
            n = n / k;
        } else {
            k++;
        }
    }
}

递归方式 二

递归方法二: (for...) 4行代码

public static String recfun2(int n) {
    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return i + "*" + recfun2(n / i);
        }
    }
    return "" + n;
}