;group=1
創(chuàng)新互聯(lián)于2013年創(chuàng)立，是專業(yè)互聯(lián)網技術服務公司，擁有項目網站建設、成都網站建設網站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元鎮(zhèn)海做網站,已為上家服務,為鎮(zhèn)海各地企業(yè)和個人服務,聯(lián)系電話:18980820575
【求助啊】分解因式 c語言 檢舉 | 離問題結束還有 14 天 3 小時 提問者：浮云的守護者 | 懸賞分：30 | 瀏覽次數(shù)：40次
給出一個正整數(shù)a，要求分解成若干個正整數(shù)的乘積，即a = a1 * a2 * a3 * ... * an，并且1 a1 = a2 = a3 = ... = an，問這樣的分解的種數(shù)有多少。注意到a = a也是一種分解。
輸出應是一個正整數(shù)，指明滿足要求的分解的種數(shù)
例子，20有4種表示方法問題補充：
說思路把我說明白也可以~~
謝謝了
需要指出，你所說的是“因數(shù)分解”（小學數(shù)學學習的內容）而非中學才學的“因式分解”（后者在計算機上實現(xiàn)的難度要大很多）。當然，“因數(shù)分解”不包括只有一個因數(shù)的情況。
對于本題，想必是給中學生的競賽題目，不需大動干戈建立質數(shù)庫。
至少有兩種思路。一按照字典序逐個生成各種分解，如20的分解：(2, 2, 5)、(2, 10)、(4, 5)、(20)在字典序下依次遞增，按照這種順序依次生成各種分解方式。另外一種是按照分解后的因數(shù)個數(shù)逐類生成，每一類按照字典序逐個生成，例如，對于20，一個因數(shù)的情形一種，(20)；兩個因數(shù)的情形兩種：(2, 10)、(4, 5)；三個因數(shù)的情形一種(2, 2, 5)；四個及以上的因數(shù)的情形0種。
為節(jié)約空間，先估計一個不太大的因數(shù)個數(shù)的上限，最簡單的方法就是找到所給整數(shù)a（不妨假定為正整數(shù)）的最小素因數(shù)，設為b1，令n=[log_b1 (a)]（以b1為底的a的對數(shù)取整，用C語言表示為n=(int)(log(1.0*a)/log(b1*1.0)）。
如果要精確一點，以節(jié)省空間（特別是當a比較大時，這是必須的），可以先找出所有素因子的個數(shù)（包括重復），以確定分解后最多有多少個因數(shù)，也不復雜，可以這樣確定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個因數(shù)直積，用2個數(shù)組分別表示各個因數(shù)以及各個因數(shù)的大致取值范圍。用A[n]表示各個因數(shù)，B[n]表示各個因數(shù)的范圍
除去只有一個因數(shù)的情況，a至少要分解為兩個因數(shù)A[1]*A[2]，其中A[1]=A[2]，所以A[1]=(int)(sqrt(a))，遍歷時A[1]只需從b1（a的最小素因數(shù)）遍歷到(int)(sqrt(a))即可。如果只找分解為兩個因數(shù)的情況，這就足夠了。對a/A[1]==0的A[1]，設E[1]=a/A[1]，如果A[1]*A[1]=E[1]，則還可以分解為3個因數(shù)的乘積，其中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個因數(shù)的乘積，其中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]遍歷完所有情況為止。
遍歷程序只需要把上面的求素因數(shù)個數(shù)的程序修改一下即可。
一個可行的程序如下：
#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.
#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請輸入正整數(shù)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是素數(shù)\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++;
}
}
}
#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ù)根\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);}
【解題思路】
對一個數(shù)進行因式分解，可以采用遞歸的辦法，先找出這個數(shù)最小的因式，然后再把這個數(shù)除以因式，繼續(xù)找，直到除到這個數(shù)成為質數(shù)為止。比如要對60進行因式分解，可以先找到60的最小因式2；然后再把60除以2得到30，接著找30的最小因式得到2；再把30除以2得到15，接著找15的最小因式3；然后再把15除以3得到5；然后5是質數(shù)，無法再分解，最終就得到60的因式共有4個，分別是2，2，3，5。而判斷一個數(shù)b是不是另一個數(shù)a的因式必須符合兩個標準，一是a必須能被b整除；二是b必須是質數(shù)。根據(jù)以上思路，代碼如下：（為了簡化程序，這里把判斷是否質數(shù)和分解因式都分別做成一個獨立的函數(shù)）
【程序代碼】
#include?iostream?????????????//控制臺操作頭文件
#include?math.h???????????????//數(shù)學函數(shù)頭文件?
//---------------?
bool?SS(int?a)??????????????????//質數(shù)判斷函數(shù)(質數(shù)返回1,否則0)
{if(a2)?return?false;??????????//小于2的數(shù)都不是質數(shù),返回0
if(a==2)?return?true;??????????//2是特殊的質數(shù)?
int?i,n=(int)sqrt(a);??????????//n是除數(shù),開方可以減少檢測個數(shù)?
for(i=2;i=n;i++)??????????????//逐個檢測能不能被整除?
if(a%i==0)?return?false;???//如果能被整除說明不是質數(shù),?返回0;??return?true;}?????????????????//檢測完了還沒可以被整除的數(shù),返回1
//---------------
void?Ys(int?s[],int?a)???????????//因式分解的遞歸函數(shù)
/*s是存放各個因式的數(shù)組,其中s[0]為因式個數(shù),a是要分解因素的數(shù)字*/
{int?i,n;???????????????????????//循環(huán)變量和因式個數(shù)
n=++s[0];??????????????????????//每遞歸調用一次因式個數(shù)增加1
if(SS(a))?{s[n]=a;?return?;}???//如果a是質數(shù),沒有因式,函數(shù)結束
for(i=2;ia;i++)???????????????//由小到大找出a的第一個因式
if(SS(i)a%i==0)?break;???//如果i是質數(shù)并且a可以被i整除
s[n]=i;????????????????????????//保存這個因式
Ys(s,a/i);}????????????????????//遞歸調用函數(shù)繼續(xù)分解下個因式
//---------------?
int?main()??????????????????????????????//主函數(shù)
{int?a,i;???????????????????????????????//整型變量?
int?S[100];????????????????????????????//用于存放因式的數(shù)組
for(;;)????????????????????????????????//弄一個無窮循環(huán)?
{printf("請輸入一個正整數(shù)(-1結束):");?//顯示提示信息
scanf("%d",a);????????????????????//從鍵盤輸入一個整數(shù)
if(a==-1)?break;???????????????????//如果輸入-1退出循環(huán)
if(a0)?continue;??????????????????//如果輸入不是正數(shù)重新輸入
S[0]=0;????????????????????????????//因式個數(shù)清零
Ys(S,a);???????????????????????????//調用函數(shù)分解因式
printf("%d共有%d個因式,分別是:",a,S[0]);//顯示因式個數(shù)
for(i=1;i=S[0];i++)?printf("%d?",S[i]);//顯示各個因式
printf("\n\n");}???????????????????//顯示完所有因式換行
printf("\n");??????????????????????????//結束程序前再空一行
system("PAUSE");???????????????????????//屏幕暫停查看顯示結果
return?0;}?????????????????????????????//結束程序
【運行結果】
以上程序在DEV?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;
}
重慶分公司
重慶分公司
