本文主要是介绍Eddy's research I HDU - 1164(DFS大爆搜)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
红红最近喜欢上了一个叫做素数的东西，她发现，所有的数都能够被分解成几个素数的乘积，可是她太懒了，所以想请你写一个程序来完成这个过程。
Input
多组输入数据，每组数据占一行，包含一个数x(1<x<=65535)
Output
在一行内输出符合题意的解（如果有多个素数因子则按字典序输出）
Sample Input
3
292Sample Output
3
2*2*73对于这类题目，我一开始没有什么思路，看到数据后，发现数据量不是很大，而且这个数据是由质数因子相乘得到的，我们就可以进行素数打表 ，和进行取余是否为0，进行剪枝。剪完枝后，时间就少了很多，就可以过了。代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<bits/stdc++.h>
#include<set>
#include<vector>
#include<cmath>
const int maxn=100050;
using namespace std;
#include<map>
#include<string>
#include<string.h>
typedef long long ll;
typedef pair<int,int> p;bool vis[maxn];
int Prime[maxn];
int cnt;
int n;
void fun()
{cnt = 0;memset(vis,true,sizeof(vis));vis[0] = vis[1] = false; vis[2] = true;for(int i = 2 ; i<=maxn; i++){if(vis[i]){Prime[cnt++] = i;for(int j = i+i ; j<=maxn; j+=i){vis[j] = false;}}}
}int a[maxn];
bool flag=false;void dfs(int x,int now,int xiabiao,int i)
{if(x%now!=0)return ;if(flag)return ;if(now>x)return ;if(Prime[i]>x)return ; if(now==x){for(int j=0;j<xiabiao;j++){if(j)cout<<"*";cout<<a[j];}flag=true;return ;} a[xiabiao]=Prime[i];dfs(x,now*Prime[i],xiabiao+1,i+1);dfs(x,now*Prime[i],xiabiao+1,i);dfs(x,now,xiabiao,i+1);return ;
}int main()
{fun();int x;while(scanf("%d",&x)!=EOF){flag=false;dfs(x,1,0,0);cout<<endl;}return 0;
}因为质数因子之间可以有重复的情况，所以我们需要三重DFS ，1.当前拿走 2.当前不拿走3.再拿走当前的一个 ，这个DFS 就好像是这几种方法，把这3个递归 放在一起，就是要让他们相互交错得到更多的结果。原理就是这样，理解了，代码就会很简单。一定要记得剪枝，不然TLE 到死。
然后就是打表的技巧，我们一定要记得，这样在你没有 模板的时候，也能拿分(蓝桥杯)。
上面是最傻的纯暴力解法，当你实在不会解题目时，你就可以使用大暴力，来拿一点样例分数。
下面我看看牛逼优秀的代码和思路：
#include<iostream>
using namespace std;
const int maxn=10000006;
typedef long long ll;
#include<bits/stdc++.h>
#include<map>
#include<set>
set<ll>s;int cnt;
bool vis[maxn];
int prime[maxn];void fun()
{cnt=0;memset(vis,true,sizeof(vis));vis[0]=vis[1]=false;vis[2]=true;for(int i=2;i<=maxn;i++){if(vis[i]){prime[cnt++]=i;for(int j=i+i;j<=maxn;j+=i)vis[j]=false; } }//cout<<prime[cnt-1]<<endl;
}int main()
{fun();ll n;while(cin>>n){vector<int>s;ll num=n;for(ll i=0;prime[i]*prime[i]<=n;i++){if(n%prime[i]==0){while(n%prime[i]==0){ n=n/prime[i];s.push_back(prime[i]);}}}if(n>1)s.push_back(n);for(int i=0;i<s.size();i++){if(i)cout<<"*";cout<<s[i];}cout<<endl;}return 0;
}我的这个素数相关知识不是很好，所以我先复习一下我的素数知识：这个素数判断是 从2一直到他的开根号的那个数据。(好菜啊我，一开始学C语言，老师就说过这个问题)，我都没有在意这个。
想一想，若2都不能除尽，还要试4, 6, 8, …吗？若3都不能除尽，还要试9, 15, 21, …吗？等等。一个数，如果有因子的话，那么在它的平方根数以内就应该有，否则就没有因子。所以必定有一个因子不大于m的平方根。故判断m是否为素数，只要试除到m的平方根就可以了，不必一直到m-1。
上面这个筛选素数因子，也是这样子，直接prime[i]*prime[i]<=m(这个数据)，就把从一开始到这个 m数据，简化了一下，减少了一点时间。这个就是 在for 循环 内用了一个while循环，将所有这个的因子都除干净，然后再进行下一个素数的分解, 最后了再将最后一个除不尽的数据再加到 vector 中 ，最后输出。
还有一个题目 ，与这个是完全相同的写法，完全一样。 是个蓝桥被系统里面的一道题目：
问题描述
给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1
输入格式
一个整数，表示n
输出格式
输出一行，包含一个整数p。
样例输入
1000
样例输出
10
数据规模和约定
n<=10^12
样例解释：n=1000=2^3*5*3，p=2*5=10
我就直接放代码吧：
#include<iostream>
using namespace std;
const int maxn=100005;
typedef long long ll;
#include<bits/stdc++.h>
#include<map>
#include<set>
set<ll>s;int a[maxn];int cnt;
bool vis[maxn];
int prime[maxn];void fun()
{cnt=0;memset(vis,true,sizeof(vis));vis[0]=vis[1]=false;vis[2]=true;for(int i=2;i<=maxn;i++){if(vis[i]){prime[cnt++]=i;for(int j=i+i;j<=maxn;j+=i)vis[j]=false; } }
}int main()
{fun();ll n;cin>>n;ll sum=1;for(ll i=0;prime[i]*prime[i]<=n;i++){if(n%prime[i]==0){sum*=prime[i];while(n%prime[i]==0)n=n/prime[i];}}sum*=n;cout<<sum<<endl;return 0;
}
这篇关于Eddy's research I HDU - 1164(DFS大爆搜)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
