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

问题描述:

求出区间[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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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();
}

}
}

普通方式-循环

普通方式, 循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 ..) 自己写的递归, 略繁琐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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行代码

1
2
3
4
5
6
7
8
public static String recfun2(int n) {
for (int i = 2; i < n; ++i) {
if (n % i == 0) {
return i + "*" + recfun2(n / i);
}
}
return "" + n;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×