【求助啊】分解因式 c语言

;group=1

创新互联于2013年创立，是专业互联网技术服务公司，拥有项目网站建设、成都网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元镇海做网站,已为上家服务,为镇海各地企业和个人服务,联系电话:18980820575

【求助啊】分解因式 c语言 检举 | 离问题结束还有 14 天 3 小时 提问者：浮云的守护者 | 悬赏分：30 | 浏览次数：40次

给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 a1 = a2 = a3 = ... = an，问这样的分解的种数有多少。注意到a = a也是一种分解。

输出应是一个正整数，指明满足要求的分解的种数

例子，20有4种表示方法问题补充：

说思路把我说明白也可以~~

谢谢了

需要指出，你所说的是“因数分解”（小学数学学习的内容）而非中学才学的“因式分解”（后者在计算机上实现的难度要大很多）。当然，“因数分解”不包括只有一个因数的情况。

对于本题，想必是给中学生的竞赛题目，不需大动干戈建立质数库。

至少有两种思路。一按照字典序逐个生成各种分解，如20的分解：(2, 2, 5)、(2, 10)、(4, 5)、(20)在字典序下依次递增，按照这种顺序依次生成各种分解方式。另外一种是按照分解后的因数个数逐类生成，每一类按照字典序逐个生成，例如，对于20，一个因数的情形一种，(20)；两个因数的情形两种：(2, 10)、(4, 5)；三个因数的情形一种(2, 2, 5)；四个及以上的因数的情形0种。

为节约空间，先估计一个不太大的因数个数的上限，最简单的方法就是找到所给整数a（不妨假定为正整数）的最小素因数，设为b1，令n=[log_b1 (a)]（以b1为底的a的对数取整，用C语言表示为n=(int)(log(1.0*a)/log(b1*1.0)）。

如果要精确一点，以节省空间（特别是当a比较大时，这是必须的），可以先找出所有素因子的个数（包括重复），以确定分解后最多有多少个因数，也不复杂，可以这样确定n。

D=a;

m=(int)(sqrt(D))+1, n=0, c=2;

while (mc)

{ if(D%c==0)

{ n++;

printf("%d", c);

D=D/c;

if(D==1) break;

else printf(", ", c);

m=(int)(sqrt(D))+1;

}

else c++;

if(m=c) { n++; printf("%d ", D); break; }

}

printf(")\n The number of prime factors of the integer is %d.\n", n);

下面讨论如何用第一种思路给出a的所有分解（楼主可以自行考虑第二种思路，难度是一样的；但是第一种方法可以减少一些重复计算又不增大空间开销）。

由于a至多可以分解为n个因数直积，用2个数组分别表示各个因数以及各个因数的大致取值范围。用A[n]表示各个因数，B[n]表示各个因数的范围

除去只有一个因数的情况，a至少要分解为两个因数A[1]*A[2]，其中A[1]=A[2]，所以A[1]=(int)(sqrt(a))，遍历时A[1]只需从b1（a的最小素因数）遍历到(int)(sqrt(a))即可。如果只找分解为两个因数的情况，这就足够了。对a/A[1]==0的A[1]，设E[1]=a/A[1]，如果A[1]*A[1]=E[1]，则还可以分解为3个因数的乘积，其中A[2]的遍历范围从A[1]到(int)(sqrt(E[1]))；如此重复，对E[1]/A[2]==0的A[2]，设E[2]=E[1]/A[2]，如果A[2]*A[2]=E[2]，则还可以分解为4个因数的乘积，其中A[3]的遍历范围从A[2]到(int)(sqrt(E[2]))；……

直到对某个k，使得A[k]*A[k]E[k]，令A[k+1]=E[k]。这样，得到一个分解方式：a=A[1]*A[2]*……*A[k]*A[k+1]。

回溯时，令A[k]自加，如果E[k-1]%A[k]==0，又得到另外一种分解方式。当A[k]的所有情况都遍历完之后，令 A[k-1]自加重新进行遍历。

直到A[1]遍历完所有情况为止。

遍历程序只需要把上面的求素因数个数的程序修改一下即可。

一个可行的程序如下：

#include stdio.h

#include malloc.h

#include math.h

main()

{ int a, b, c, n, F, F1, D, num, i, I, m;

int *A=NULL, *B=NULL, *E=NULL;

printf("\n This program will get the number of unsorted factorizations of a given integer. Please input a positive interger greater than 1.\n The number input: ");

scanf("%d", a);

if(a2)

{ printf("\n Input Error. The integer you input is not valid.\n");

return 0;

}

printf("\n The Prime factors of the given integer %d are as follow: \n \t ( ", a);

D=a;

m=(int)(sqrt(D))+1, n=0, c=2;

while (mc)

{ if(D%c==0)

{ n++;

printf("%d", c);

D=D/c;

if(D==1) break;

else printf(", ", c);

m=(int)(sqrt(D))+1;

}

else c++;

if(m=c) { n++; printf("%d ", D); break; }

}

printf(")\n The number of prime factors of the integer is %d.\n", n);

if(n==1)

{ printf("\n The integer you input is a prime. The number of unsorted factorizations is 1.\n");

return 1;

}

A=(int*)malloc(sizeof(int)*(n+1));

if(A==NULL)

{ printf("\n Error. Can not get enough space in the memory.\n");

return 0;

}

B=(int*)malloc(sizeof(int)*(n+1));

if(B==NULL)

{ printf("\n Error. Can not get enough space in the memory.\n");

return 0;

}

E=(int*)malloc(sizeof(int)*(n+1));

if(E==NULL)

{ printf("\n Error. Can not get enough space in the memory.\n");

return 0;

}

E[0]=a, A[0]=2, A[1]=1, num=0;

B[1]=(int)(sqrt(E[0]))+1;

I=1;

while (I0 I=n)

{ F=0, F1=0;

// printf("\n I=%d, B[I]=%d, E[I-1]=%d, A[I-1]=%d. ", I, B[I], E[I-1], A[I-1]);

//if(In) { printf("\n Error. I=%dn=%d.\n", I, n); return -1; }

for( A[I]++; A[I]B[I]; A[I]++)

{ //printf("\n A[I]=%d, ", A[I]);

if(E[I-1]%A[I]==0)

{ //printf(" valid.");

E[I]=E[I-1]/A[I]; F++, F1++;

if( E[I]A[I]*A[I] F1==0) // E[I] !=1

{ printf("\n A valid factorization : %d=", a);

if(I0) printf("%d", A[1]);

if(I1) for(i=2; iI; i++) printf("*%d", A[i]);

printf("*%d", E[I]);

num++;

F=0;

}

else // F1!=0 || E[I]=A[I]*A[I]

{ B[I+1]=(int)(sqrt(E[I]))+1; A[I+1]=A[I]-1; I++; break; }

} //end if(E[I-1]%A[I]==0)

//else printf(" not valid.");

} // end loop I

if (F==0 F1==0) // E[I-1] is not divisible by all possible A[I].

{ printf("\n A valid factorization : %d=", a);

if(I1)

{ printf("%d*", A[1]);

for(i=2; iI; i++) printf("%d*", A[i]);

}

printf("%d", E[I-1]);

num++, I--;

}

} // while (I0)

printf("\n The number of unsorted factorizations of the given integer is %d.\n", num);

free(A);

free(B);

free(E);

return 1;

}

通过gcc编译，当输入20时，结果如下：

This program will get the number of unsorted factorizations of a given integer. Please input a positive interger greater than 1.

The number input: 20

The Prime factors of the given integer 20 are as follow:

( 2, 2, 5 )

The number of prime factors of the integer is 3.

A valid factorization : 20=2*2*5

A valid factorization : 20=2*10

A valid factorization : 20=4*5

A valid factorization : 20=20

The number of unsorted factorizations of the given integer is 4.

当输入36时，结果如下

This program will get the number of unsorted factorizations of a given integer. Please input a positive interger greater than 1.

The number input: 36

The Prime factors of the given integer 36 are as follow:

( 2, 2, 3, 3 )

The number of prime factors of the integer is 4.

A valid factorization : 36=2*2*3*3

A valid factorization : 36=2*2*9

A valid factorization : 36=2*3*6

A valid factorization : 36=2*18

A valid factorization : 36=3*3*4

A valid factorization : 36=3*12

A valid factorization : 36=4*9

A valid factorization : 36=6*6

A valid factorization : 36=36

The number of unsorted factorizations of the given integer is 9.

C语言 因式分解

#includestdio.h

#includestdlib.h

#includestring.h

unsigned int m=2;

unsigned int cnt=1;

void Factor(int n, char *msg, char printYes);

int main()

{

char s[100]={0};

char flag='y';

printf("------求整数的因式分解------\n请输入正整数m(1):");

scanf("%u", m);

printf("打印详细分解情况吗？[y|n，回车打印]");

scanf("%*c%c",flag);

if(m1)

{

printf("error input!\n");

exit(-1);

}

if(flag!='n')

printf("%d =  %d \n", m,m);

Factor(m, s,flag);

if(cnt==1)

printf("\n%d是素数\n",m);

printf("\n------");

printf("一共有%d种", cnt);

printf("------\n");

return 0;

}

void Factor(int n, char *msg,char printYes)

{

char s2[100]={0};//保存当前分解的部分结果

if(n==1)

return ;

for(int i=2;in;i++)

{

if (n%i==0)

{

if(n==m)

sprintf(msg, "%d = ", m);

sprintf(s2,"%s %d * ",msg, i);//因式分解部分结果保存在字符串s2中

if(printYes!='n')

printf("%s %d\n",s2,n/i);//打印结果（包括最后一个因子）

Factor(n/i,s2,printYes);

cnt++;

}

}

}

c语言——一元二次函数因式分解

#include#includevoidm(floata,floatb,floatc){doublex1,x2;x1=(-b+sqrt(b*b-4*a*c))/(2*a);x2=(-b-sqrt(b*b-4*a*c))/(2*a);printf("方程的根是%.2lf和%.2lf",x1,x2);}voidn(floata,floatb,floatc){doublex;x=(-b)/(2*a);printf("方程的根为%.2lf",x);}voidf(floata,floatb,floatc){printf("方程无实数根\n");}main(){floata,b,c;printf("请输入a,b,c的值\n");scanf("%f%f%f",a,b,c);if(b*b-4*a*c0)m(a,b,c);if(b*b-4*a*c==0)n(a,b,c);if(b*b-4*a*c0)f(a,b,c);}

c++/c语言因式分解

【解题思路】

对一个数进行因式分解，可以采用递归的办法，先找出这个数最小的因式，然后再把这个数除以因式，继续找，直到除到这个数成为质数为止。比如要对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(a2) 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;ia;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(a0) 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++上运行通过。

截图如下：

C语言因式分解

// 下面是用我在toj 10004上面通过的代码，稍加修改写成的。

#include stdio.h

#include math.h

int Prime(int x)

{

int n, i;

n = (int)sqrt(x);

for (i = 2; i = n; i++)

if (x % i == 0) break;

if (i n)

return 1;

else

return 0;

}

int main()

{

// freopen("2.txt","w",stdout);

int x;

int t;

int i , n;

int y;

int first;

int max;

while (scanf("%d",max) == 1)

{

for (y = 2; y = max; y++)

{

x = y;

if (Prime(x))

{

printf("%d=%d\n",x,x);

}

else

{

printf("%d=",x);

first = 1;

do

{

for (i = 2; i = x; i++)

{

t = 0; n = 0;

while (x % i == 0)

{

t = 1;

n++;

x = x/i;

}

if (t)

{

if (first) first = 0;

else printf("*");

while (n1)

{

printf("%d*",i);

n--;

}

printf("%d",i);

}

}

} while(x != 1);

printf("\n");

}

}

}

return 0;

}