又是一道水到不能再水的题，用递归+递推
首先是判断素数
i从2开始，如果n能整除i，说明n是合数（非素数），直接return 0，循环一遍后，如果都不能整除，说明是素数，return 1。（其实就是穷举）
代码如下 :
```cpp
int prime(int a)
{
for(int i=2;i<=sqrt(a);i++)
if(a%i==0)return 0;
return 1;
}
```
然后就是递归
其中n是要分解的数，for从2开始，一直到n，如果i能被n整除&&是素数，就输出i
代码如下 ：
```cpp
void dfs(int n)//递归函数
{
if(n==1)return ;//停止条件
for(int i=2;i<=n;i++)
{
if(n%i==0&&prime(i))//从2开始，如果是素数&&能被n整除就输出i
{
if(n/i==1)//特判：消掉最后一个"*"号
cout<<i;
else
cout<<i<<'*';//输出i和*
return dfs(n/i);//继续递归
}
}
}
```
最后就是斐波那契
用递推公式f[i]=f[i-1]+f[i-2]
代码如下 ：
```cpp
for(int i=3;i<=n;i++)
f[i]=f[i-1]+f[i-2];
```
最后，献上完整代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>//数学库
#include<cstring>
#include<algorithm>
using namespace std;
const long long p=pow(2,31);
int prime(int a)//素数的判定
{
for(int i=2;i<=sqrt(a);i++)
if(a%i==0)return 0;
return 1;
}
void dfs(int n)//递归函数
{
if(n==1)return ;//停止条件
for(int i=2;i<=n;i++)
{
if(n%i==0&&prime(i))//从2开始，如果是素数&&能被n整除就输出i
{
if(n/i==1)//特判：消掉最后一个"*"号
cout<<i;
else
cout<<i<<'*';//输出i和*
return dfs(n/i);//继续递归
}
}
}
int main()
{
int n;
cin>>n;
int f[p];//斐波那契数组
f[1]=1,f[2]=1;//定义f[1] ,f[2];
for(int i=3;i<=n;i++)//斐波那契
f[i]=(f[i-1]+f[i-2])%p;
cout<<f[n]<<"=";//先输出f[n]=
dfs(f[n]);//递归调用
return 0;//愉快的结束
}
```
by Lates @ 2018-11-03 12:32:45