原文: 藍(lán)橋杯算法練習(xí) - 分解質(zhì)因數(shù)
date: 2014-11-14 12:39:04
問(wèn)題描述：
求出區(qū)間[a,b]中所有整數(shù)的質(zhì)因數(shù)分解茬暇。
輸入格式：
輸入兩個(gè)整數(shù)a首昔，b。
輸出格式：
每行輸出一個(gè)數(shù)的分解糙俗，形如k=a1a2a3…(a1<=a2<=a3…勒奇，k也是從小到大的)(具體可看樣例)
樣例輸入：
3 10
樣例輸出：
3=3
4=225=56=23
7=7
8=222
9=3310=25
提示：
先篩出所有素?cái)?shù)，然后再分解巧骚。
數(shù)據(jù)規(guī)模和約定：
2<=a<=b<=10000
實(shí)現(xiàn)：
主函數(shù)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();
}
}
}
普通方式-循環(huán)
普通方式, 循環(huán)
public static void fun(int n) {
int k = 2; // --定義一個(gè)標(biāo) k
while (k <= n) {
if (n % k == 0) {
System.out.print(k);
// 若后面還有 項(xiàng), 輸出"*" 后繼續(xù)判斷
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;
}
