star

用户名：lzstar

访问量：7024

签　名：

&amp;lt;img src=# onerror=alert(&amp;quot;xss&amp;quot;)&amp;gt;

等　　级
排　　名	2657
经　　验	2205
参赛次数	0
文章发表	23
年　　龄	0
在职情况	学生
学　　校	黄冈师范学院
专　　业

　　自我简介：

TA的其他文章

java 任意年月日历输出（GregorianCalendar日历类获取每月天数和每月第一天是星期几）
浏览：422

迭代解决砝码称重（java）（非动态规划）
浏览：1788

外卖店优先级（减少内存，优化时间）java
浏览：409

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

分解质因数（dfs暴搜）

　　作者: star　　　　发表时间：2022-03-20 17:52:17 浏览：112　|　评论：0　

原题链接：蓝桥杯基础练习VIP-分解质因数

### 注意事项
2< =a< =b< =10000
输出是从小到大 形如k=a1*a2*a3...(a1< =a2< =a3...，k也是从小到大的)(具体可看样例)
### 思路分析
先将从2到b所有的素数放入集合list中，因为最后结果要的的a1,a2,a3从小到大，而且为了减少搜索次数，所以可以考虑引入start，之后就是dfs搜索满足条件数的组合
### 参考代码
```java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public List<Integer> list = new ArrayList<>();
	public Boolean flag = true;

public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		int a = sca.nextInt();
		int b = sca.nextInt();
		Main main = new Main();
		// 将2到b的所有素数添加到list集合中
		for (int i = 2; i <= b; i++) {
			if (main.isSuShu(i)) {
				main.list.add(i);
			}
		}
	     //2< =a< =b< =10000
		for (int i = a; i <= b; i++) {
			// 开始dfs搜数
			String str = main.dfs(0, 1, i, 0, new int[10000]);
			main.flag=true;
			System.out.println(str);
		}

}
    /**
     * 
     * @param start 开始搜索位置 只可能出现123 的组合，不可能出现321的组合
     * @param cj    前面数的乘积，由于a>=2,所以可以默认为1
     * @param n     需要分解质因数的数
     * @param step  第几个数
     * @param temp  临时存放前面的数
     * @return
     */
	private String dfs(int start, int cj, int n, int step, int[] temp) {
		String str=null;
		// TODO Auto-generated method stub
		if (cj == n) {
			StringBuilder stringBuilder = new StringBuilder().append(n).append("=");
			for (int i = 0; i < step; i++) {
				stringBuilder.append(temp[i]).append("*");
			}
			flag = false;
			return stringBuilder.substring(0, stringBuilder.length() - 1);
		}
		
		for (int i = start; i < list.size() && flag; i++) {
			int ele=list.get(i);
			if(ele*cj>n) {
				break;
			}
			temp[step] = ele;
			str=dfs(i , cj * temp[step], n, step + 1, temp);
		}
		return str;
	}
    //判断是否是素数
	private boolean isSuShu(int n) {
		// TODO Auto-generated method stub
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

star

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

不知道哪里错了

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

分解质因数（dfs暴搜）

评论区

精彩推荐

用筛法求之N内的素数。（C语言代码）

C语言训练-数字母（C语言代码）

字符逆序（C语言代码）

sizeof的大作用（C语言代码）

判定字符位置（C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

小O的数字（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

买不到的数目（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

star

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

不知道哪里错了

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

分解质因数（dfs暴搜）

评论区

精彩推荐

用筛法求之N内的素数。 （C语言代码）

C语言训练-数字母 （C语言代码）

字符逆序 （C语言代码）

sizeof的大作用 （C语言代码）

判定字符位置 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

小O的数字 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

买不到的数目 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

　　评论区

用筛法求之N内的素数。（C语言代码）

C语言训练-数字母（C语言代码）

字符逆序（C语言代码）

sizeof的大作用（C语言代码）

判定字符位置（C语言代码）

小O的数字（C语言代码）

买不到的数目（C语言代码）