Question

c++/c语言因式分解

Description 将大于1的自然数N进行因式分解，满足N=a1*a2*a3…am
编一程序，对任意的自然数N，
求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

Input 输入文件仅有一行包含一个整数N。Output 输出文件仅有一行包含一个整数表示自然数N的因式分解方案总数。Sample Input 12 Sample Output 8 Hint 1 <= N <= 2,000,000,000

Answer 1

【解题思路】
对一个数进行因式分解，可以采用递归的办法，先找出这个数最小的因式，然后再把这个数除以因式，继续找，直到除到这个数成为质数为止。比如要对60进行因式分解，可以先找到60的最小因式2；然后再把60除以2得到30，接着找30的最小因式得到2；再把30除以2得到15，接着找15的最小因式3；然后再把15除以3得到5；然后5是质数，无法再分解，最终就得到60的因式共有4个，分别是2，2，3，5。而判断一个数b是不是另一个数a的因式必须符合两个标准，一是a必须能被b整除；二是b必须是质数。根据以上思路，代码如下：（为了简化程序，这里把判断是否质数和分解因式都分别做成一个独立的函数）
【程序代码】
#include <iostream>             //控制台操作头文件
#include <math.h>               //数学函数头文件 

//--------------- 
bool SS(int a)                  //质数判断函数(质数返回1,否则0)
{if(a<2) return false;          //小于2的数都不是质数,返回0
 if(a==2) return true;          //2是特殊的质数 
 int i,n=(int)sqrt(a);          //n是除数,开方可以减少检测个数 
 for(i=2;i<=n;i++)              //逐个检测能不能被整除 
     if(a%i==0) return false;   //如果能被整除说明不是质数, 返回0;  return true;}                 //检测完了还没可以被整除的数,返回1
//---------------
void Ys(int s[],int a)           //因式分解的递归函数
/*s是存放各个因式的数组,其中s[0]为因式个数,a是要分解因素的数字*/
{int i,n;                       //循环变量和因式个数
 n=++s[0];                      //每递归调用一次因式个数增加1
 if(SS(a)) {s[n]=a; return ;}   //如果a是质数,没有因式,函数结束
 for(i=2;i<a;i++)               //由小到大找出a的第一个因式
     if(SS(i)&&a%i==0) break;   //如果i是质数并且a可以被i整除
 s[n]=i;                        //保存这个因式
 Ys(s,a/i);}                    //递归调用函数继续分解下个因式
//--------------- 
int main()                              //主函数
{int a,i;                               //整型变量 
 int S[100];                            //用于存放因式的数组
 
 for(;;)                                //弄一个无穷循环 
    {printf("请输入一个正整数(-1结束):"); //显示提示信息
     scanf("%d",&a);                    //从键盘输入一个整数
     if(a==-1) break;                   //如果输入-1退出循环
     if(a<0) continue;                  //如果输入不是正数重新输入
     S[0]=0;                            //因式个数清零
     Ys(S,a);                           //调用函数分解因式
     printf("%d共有%d个因式,分别是:",a,S[0]);//显示因式个数
     for(i=1;i<=S[0];i++) printf("%d ",S[i]);//显示各个因式
     printf("\n\n");}                   //显示完所有因式换行
 printf("\n");                          //结束程序前再空一行
 system("PAUSE");                       //屏幕暂停查看显示结果
 return 0;}                             //结束程序
 
【运行结果】
以上程序在DEV C++上运行通过。

截图如下：

Answer 2

这个问题真要做的话是很难的。下面是一个比较简单的算法，基本思想是先求素数表，再求质因子分解，最后求组合。// pku 3421 给一个整数X,求X的分解。1=X0,X1,X2,...,Xm=X，其中Xi整除X(i+1)且Xi<X(i+1)，要求最大的m跟有多少种这样长度的链。
// 算法：因为m要最大，所以每次Xi只能乘以一个质因子。若不然可以得到一个更短的链。
// 先求出所有的质因子，所有质因子的排列除以重复的次数就是这种链的个数. #include <iostream>
#include <math.h>using namespace std;__int64 p[172];
// 因子数目最多是20个
int e[21];
int cnt;
__int64 factor[21];void prime()
{
int i,j,flag;
p[0]=2;
p[1]=3;
cnt=2;
for(i=5;i<=1024;i+=2){
flag=0;
for(j=1;p[j]*p[j]<=i;j++){
if(i%p[j]==0) {flag=1;break;}
}
if(!flag) p[cnt++]=i;
}
}// 先质因子分解，再求组合的个数
void solve(__int64 a)
{
// j统计所有质因子的个数，k统计不同质因子个数
int i,j=0,flag,l=0;
memset(e,0,sizeof(e));
// 用1024以内的素数分解a，注意到a<=2^20，a最多含有一个超过1024的质因子
// a=p1^e1*p2^e2**pk^ek*ps^es，其中只有ps是大于1024的素数，且es只能为0或1
for(i=0;i<cnt && a>1;i++){
flag=0;
while(a%p[i]==0){
flag=1;
e[l]++;
a/=p[i];
j++;
}
if(flag==1) l++;
}
// 若此时a!=1则a一定是素数
if(a!=1) {j++;e[l++]=1;}
__int64 res = factor[j];
for(i=0;i<l;i++){
if(e[i]!=0) res/=factor[e[i]];
}
printf("%d %I64d\n",j,res);
}int main()
{
prime1();
//cnt=172;
// 阶乘
factor[0]=1;
for(__int64 i=1;i<21;i++) factor[i]=factor[i-1]*i;
__int64 a;
while(scanf("%I64d",&a)!=EOF){
solve(a);
}

return 1;
}

Answer 3

/* 请修改读入和输出文件的路径和文件名，读入的文件要自己创建（我没考虑大数情况，请楼主自己补充吧）*/
#include "iostream"
#include "math.h"
#include <fstream>
using namespace std;

int g_Count_Num = 0;
void Count(int N)
{
int yinshu[20];
int yinshu_count = 0;
if(N <= 3)
{
return;
}

// 由小到大的计算N的因数 并存放在数组中(这里做了一点点优化，从2遍历到根号N，即可算出所有的因数)
for (int i=2; i <= sqrt(N);i++)
{
if ((N/i)*i == N)
{
// 将i计入因数数组中
yinshu[yinshu_count] = i;
yinshu_count++;
g_Count_Num++;

if (i*i != N)
{
// 若i 和 N/i 不想等则将 N/i也放入数组中
yinshu[yinshu_count] = N/i;
yinshu_count++;
g_Count_Num++;
}
}
}
// 在将位于后边的每个因数再次分解一次
for (i = 0;i < yinshu_count;i++)
{
Count(N/(yinshu[i]));
}
}

void main()
{
// 读数据
int N = 0;
ifstream in_file;
in_file.open("D:/input.txt");//这里修改读入文件的路径
if (in_file == NULL)
{
cout<<"读入文件错误或不存在"<<endl;
return;
}
in_file>>N;
in_file.close();

ofstream out_file;

// 求N的可分解数目 Count(N);
//最后加上自身的那种情况
g_Count_Num++;
out_file.open("D:/output.txt");
if (out_file == NULL)
{
cout<<"输出文件错误或不存在"<<endl;
return;
}
out_file<<g_Count_Num<<endl;
out_file.close();
}

// 纯手写，望采纳、

Answer 4

这么难的题目连分都没有呀？！
#include "stdio.h"
#include "stdlib.h"
#include "ctype.h"
typedef int Integer[100];
Integer s;
int t=0;
int D;
void dd(int m,int n);
int main()
{
printf("输入一个大于3的正整数:");
do
{
scanf("%d",&D);
if(D<=3)
{
printf("输入错误,请重新输入!");
}
else
{
break;
}
}while(D>3);
printf("%d=%d\n",D,D);
dd(2,D);
}
void dd(int m,int n)
{
int i,j,k;
i=m;
j=n;
if(i<j)
{
if(j % i==0)
{
t=t+1;
s[t]=i;
for(k=1;k<=t;k++)
{
printf("%d*",s[k]);
}
printf("%d=%d\n",j/i,D);
dd(2,n/i);
t=t-1;
dd(i+1,j);
}
else
{
dd(i+1,j);
}
}
}

Answer 5

用递归算法