原文: 蓝桥杯算法练习 - 分解质因数
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;
}
