因式分解

因式分解

时间: 1ms        内存:64M

描述:

将大于1的自然数N进行因式分解,满足N=a1*a2*a3…*am。
编一程序,对任意的自然数N(1<N<=2,000,000,000),求N的所有形式不同的因式分解方案总数。如N=12,共有8种分解方案,他们分别是:
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

输入:

输入只有一行,一个整数N

输出:

输出只有一行,一个整数表示自然数N的因式分解方案总数

示例输入:

12

示例输出:

8

提示:

参考答案(内存最优[748]):

#include<stdio.h>  
int count=0;  
int n;  
void solve(int m)  
{  
    int i;  
    for(i=2;i<=m;i++)
	{  
        if(m%i==0)
		{  
            if(m/i==1)
			{  
                count++;  
                return ;  
            }  
            solve(m/i);  
        }  
    }  
}  
int main()  
{ 
    while(scanf("%d",&n)==1)
	{  
        count=0;  
        solve(n);  
        printf("%d\n",count);  
    }  
    return 0;    
}  

参考答案(时间最优[0]):

#include <iostream>
using namespace std;
int count=0;
int main()
{
    void f(int n);
    int n;
    cin>>n;
    f(n);
    cout<<count<<endl;
    return 0;
}
void f(int n)
{
    int i;
    for(i=1;i<n;i++)
    {
        if(i==1)
        {
            count++;
            continue;
        }
        if(n%i==0)
        {
            f(n/i);
        }
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注