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

;group=1

創(chuàng)新互聯(lián)于2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元鎮(zhèn)海做網(wǎng)站,已為上家服務(wù),為鎮(zhèn)海各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575

【求助啊】分解因式 c語言 檢舉 | 離問題結(jié)束還有 14 天 3 小時(shí) 提問者：浮云的守護(hù)者 | 懸賞分：30 | 瀏覽次數(shù)：40次

給出一個(gè)正整數(shù)a，要求分解成若干個(gè)正整數(shù)的乘積，即a = a1 * a2 * a3 * ... * an，并且1 a1 = a2 = a3 = ... = an，問這樣的分解的種數(shù)有多少。注意到a = a也是一種分解。

輸出應(yīng)是一個(gè)正整數(shù)，指明滿足要求的分解的種數(shù)

例子，20有4種表示方法問題補(bǔ)充：

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

謝謝了

需要指出，你所說的是“因數(shù)分解”（小學(xué)數(shù)學(xué)學(xué)習(xí)的內(nèi)容）而非中學(xué)才學(xué)的“因式分解”（后者在計(jì)算機(jī)上實(shí)現(xiàn)的難度要大很多）。當(dāng)然，“因數(shù)分解”不包括只有一個(gè)因數(shù)的情況。

對(duì)于本題，想必是給中學(xué)生的競賽題目，不需大動(dòng)干戈建立質(zhì)數(shù)庫。

至少有兩種思路。一按照字典序逐個(gè)生成各種分解，如20的分解：(2, 2, 5)、(2, 10)、(4, 5)、(20)在字典序下依次遞增，按照這種順序依次生成各種分解方式。另外一種是按照分解后的因數(shù)個(gè)數(shù)逐類生成，每一類按照字典序逐個(gè)生成，例如，對(duì)于20，一個(gè)因數(shù)的情形一種，(20)；兩個(gè)因數(shù)的情形兩種：(2, 10)、(4, 5)；三個(gè)因數(shù)的情形一種(2, 2, 5)；四個(gè)及以上的因數(shù)的情形0種。

為節(jié)約空間，先估計(jì)一個(gè)不太大的因數(shù)個(gè)數(shù)的上限，最簡單的方法就是找到所給整數(shù)a（不妨假定為正整數(shù)）的最小素因數(shù)，設(shè)為b1，令n=[log_b1 (a)]（以b1為底的a的對(duì)數(shù)取整，用C語言表示為n=(int)(log(1.0*a)/log(b1*1.0)）。

如果要精確一點(diǎn)，以節(jié)省空間（特別是當(dāng)a比較大時(shí)，這是必須的），可以先找出所有素因子的個(gè)數(shù)（包括重復(fù)），以確定分解后最多有多少個(gè)因數(shù)，也不復(fù)雜，可以這樣確定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的所有分解（樓主可以自行考慮第二種思路，難度是一樣的；但是第一種方法可以減少一些重復(fù)計(jì)算又不增大空間開銷）。

由于a至多可以分解為n個(gè)因數(shù)直積，用2個(gè)數(shù)組分別表示各個(gè)因數(shù)以及各個(gè)因數(shù)的大致取值范圍。用A[n]表示各個(gè)因數(shù)，B[n]表示各個(gè)因數(shù)的范圍

除去只有一個(gè)因數(shù)的情況，a至少要分解為兩個(gè)因數(shù)A[1]*A[2]，其中A[1]=A[2]，所以A[1]=(int)(sqrt(a))，遍歷時(shí)A[1]只需從b1（a的最小素因數(shù)）遍歷到(int)(sqrt(a))即可。如果只找分解為兩個(gè)因數(shù)的情況，這就足夠了。對(duì)a/A[1]==0的A[1]，設(shè)E[1]=a/A[1]，如果A[1]*A[1]=E[1]，則還可以分解為3個(gè)因數(shù)的乘積，其中A[2]的遍歷范圍從A[1]到(int)(sqrt(E[1]))；如此重復(fù)，對(duì)E[1]/A[2]==0的A[2]，設(shè)E[2]=E[1]/A[2]，如果A[2]*A[2]=E[2]，則還可以分解為4個(gè)因數(shù)的乘積，其中A[3]的遍歷范圍從A[2]到(int)(sqrt(E[2]))；……

直到對(duì)某個(gè)k，使得A[k]*A[k]E[k]，令A(yù)[k+1]=E[k]。這樣，得到一個(gè)分解方式：a=A[1]*A[2]*……*A[k]*A[k+1]。

回溯時(shí)，令A(yù)[k]自加，如果E[k-1]%A[k]==0，又得到另外一種分解方式。當(dāng)A[k]的所有情況都遍歷完之后，令 A[k-1]自加重新進(jìn)行遍歷。

直到A[1]遍歷完所有情況為止。

遍歷程序只需要把上面的求素因數(shù)個(gè)數(shù)的程序修改一下即可。

一個(gè)可行的程序如下：

#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編譯，當(dāng)輸入20時(shí)，結(jié)果如下：

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.

當(dāng)輸入36時(shí)，結(jié)果如下

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("------求整數(shù)的因式分解------\n請(qǐng)輸入正整數(shù)m(1):");

scanf("%u",?m);

printf("打印詳細(xì)分解情況嗎？[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是素?cái)?shù)\n",m);

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

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

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

return?0;

}

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

{

char?s2[100]={0};//保存當(dāng)前分解的部分結(jié)果

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);//因式分解部分結(jié)果保存在字符串s2中

if(printYes!='n')

printf("%s?%d\n",s2,n/i);//打印結(jié)果（包括最后一個(gè)因子）

Factor(n/i,s2,printYes);

cnt++;

}

}

}

c語言——一元二次函數(shù)因式分解

#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("方程無實(shí)數(shù)根\n");}main(){floata,b,c;printf("請(qǐng)輸入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語言因式分解

【解題思路】

對(duì)一個(gè)數(shù)進(jìn)行因式分解，可以采用遞歸的辦法，先找出這個(gè)數(shù)最小的因式，然后再把這個(gè)數(shù)除以因式，繼續(xù)找，直到除到這個(gè)數(shù)成為質(zhì)數(shù)為止。比如要對(duì)60進(jìn)行因式分解，可以先找到60的最小因式2；然后再把60除以2得到30，接著找30的最小因式得到2；再把30除以2得到15，接著找15的最小因式3；然后再把15除以3得到5；然后5是質(zhì)數(shù)，無法再分解，最終就得到60的因式共有4個(gè)，分別是2，2，3，5。而判斷一個(gè)數(shù)b是不是另一個(gè)數(shù)a的因式必須符合兩個(gè)標(biāo)準(zhǔn)，一是a必須能被b整除；二是b必須是質(zhì)數(shù)。根據(jù)以上思路，代碼如下：（為了簡化程序，這里把判斷是否質(zhì)數(shù)和分解因式都分別做成一個(gè)獨(dú)立的函數(shù)）

【程序代碼】

#include?iostream?????????????//控制臺(tái)操作頭文件

#include?math.h???????????????//數(shù)學(xué)函數(shù)頭文件?

//---------------?

bool?SS(int?a)??????????????????//質(zhì)數(shù)判斷函數(shù)(質(zhì)數(shù)返回1,否則0)

{if(a2)?return?false;??????????//小于2的數(shù)都不是質(zhì)數(shù),返回0

if(a==2)?return?true;??????????//2是特殊的質(zhì)數(shù)?

int?i,n=(int)sqrt(a);??????????//n是除數(shù),開方可以減少檢測個(gè)數(shù)?

for(i=2;i=n;i++)??????????????//逐個(gè)檢測能不能被整除?

if(a%i==0)?return?false;???//如果能被整除說明不是質(zhì)數(shù),?返回0;??return?true;}?????????????????//檢測完了還沒可以被整除的數(shù),返回1

//---------------

void?Ys(int?s[],int?a)???????????//因式分解的遞歸函數(shù)

/*s是存放各個(gè)因式的數(shù)組,其中s[0]為因式個(gè)數(shù),a是要分解因素的數(shù)字*/

{int?i,n;???????????????????????//循環(huán)變量和因式個(gè)數(shù)

n=++s[0];??????????????????????//每遞歸調(diào)用一次因式個(gè)數(shù)增加1

if(SS(a))?{s[n]=a;?return?;}???//如果a是質(zhì)數(shù),沒有因式,函數(shù)結(jié)束

for(i=2;ia;i++)???????????????//由小到大找出a的第一個(gè)因式

if(SS(i)a%i==0)?break;???//如果i是質(zhì)數(shù)并且a可以被i整除

s[n]=i;????????????????????????//保存這個(gè)因式

Ys(s,a/i);}????????????????????//遞歸調(diào)用函數(shù)繼續(xù)分解下個(gè)因式

//---------------?

int?main()??????????????????????????????//主函數(shù)

{int?a,i;???????????????????????????????//整型變量?

int?S[100];????????????????????????????//用于存放因式的數(shù)組

for(;;)????????????????????????????????//弄一個(gè)無窮循環(huán)?

{printf("請(qǐng)輸入一個(gè)正整數(shù)(-1結(jié)束):");?//顯示提示信息

scanf("%d",a);????????????????????//從鍵盤輸入一個(gè)整數(shù)

if(a==-1)?break;???????????????????//如果輸入-1退出循環(huán)

if(a0)?continue;??????????????????//如果輸入不是正數(shù)重新輸入

S[0]=0;????????????????????????????//因式個(gè)數(shù)清零

Ys(S,a);???????????????????????????//調(diào)用函數(shù)分解因式

printf("%d共有%d個(gè)因式,分別是:",a,S[0]);//顯示因式個(gè)數(shù)

for(i=1;i=S[0];i++)?printf("%d?",S[i]);//顯示各個(gè)因式

printf("\n\n");}???????????????????//顯示完所有因式換行

printf("\n");??????????????????????????//結(jié)束程序前再空一行

system("PAUSE");???????????????????????//屏幕暫停查看顯示結(jié)果

return?0;}?????????????????????????????//結(jié)束程序

【運(yùn)行結(jié)果】

以上程序在DEV?C++上運(yùn)行通過。

截圖如下：

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;

}

分享題目：c語言用函數(shù)實(shí)現(xiàn)因式分解,高階函數(shù)分解因式
轉(zhuǎn)載注明：http://chinadenli.net/article30/hohhso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、企業(yè)建站、網(wǎng)站維護(hù)、網(wǎng)站營銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)