问题 d: 【递归入门】因式分解

时间限制: 3 Sec  内存限制: 128 MB

提交: 19  解决: 5

[][][][命题人:外部导入]

题目描述

1 < n < = 2^31 

n = a1*a2*a3*a4.......*am 

比如： 

12=12 

12=6*2 

12=4*3 

12=3*4 

12=3*2*2 

12=2*6 

12=2*3*2 

12=2*2*3 

总共8种

 

输入

 一行一个整数n（1 < n < = 2^31 ）

输出

 输出分解的总数

样例输入

12

样例输出

8

解题思路：暴力递归求解，但因为随着n的增大，所用时间会越来越多，所以必须剪枝，一共wa了2次才ac，下面附上所有的代码。

第一次wa（直接暴力递归无任何剪枝）：

#include
     
      using namespace std; int n,cnt=0; void dfs(int x){    if(x==n){cnt++;return;}    else if(x>n)return;    for(int i=2;i<=n/2;++i)    {        if(x*i>n)break;        dfs(x*i);    }} int main(){    while(cin>>n)    {        cnt=0;        dfs(1);        cout<
      
       <
      
     

第二次wa（加入了素数的判定）：

#include
     
      using namespace std; int n,cnt=0; bool is_prime(int x)//判定n是否是素数{    int j=sqrt(x);    for(int i=2;i<=j;++i)    {        if(x%i==0)return false;    }    return true;} void dfs(int x){    if(x==n){cnt++;return;}    else if(x>n)return;    for(int i=2;i<=n/2;++i)    {        if(x*i>n)break;        dfs(x*i);    }} int main(){    while(cin>>n)    {        cnt=0;        if(is_prime(n))cout<<"1"<
     

第三次ac（先找出n的所有因子保存到一个数组，并且在递归前先判定x*a[i]是否是n的因数）：

#include
     
      using namespace std; int n,cnt,j;int a[99999]; bool is_prime(int x){    int j=sqrt(x);    if(x==1||x==2)return true;    else for(int i=2;i<=j;++i)    {        if(x%i==0)return false;    }    return true;} void dfs(int x){    if(x==n){cnt++;return;}    else if(x>n)return;    for(int i=0;i
      
       n)break;        if(n%(x*a[i])==0)dfs(x*a[i]);//判定x*a[i]是否是n的因数    }} int main(){    while(cin>>n)    {        cnt=0,j=0;        memset(a,0,sizeof(a));        if(is_prime(n))cout<<"1"<