因式分解
时间: 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);
}
}
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。