Question

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

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

例子，20有4种表示方法
说思路把我说明白也可以~~

谢谢了

Answer 1

http://zhidao.baidu.com/question/346500603.html?push=reduce&group=1

【求助啊】分解因式 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 (m>c)
{ 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(a<2)
{ 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 (m>c)
{ 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 (I>0 && 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(I>n) { printf("\n Error. I=%d>n=%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(I>0) printf("%d", A[1]);
if(I>1) for(i=2; i<I; 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(I>1)
{ printf("%d*", A[1]);
for(i=2; i<I; i++) printf("%d*", A[i]);
}
printf("%d", E[I-1]);
num++, I--;
}

} // while (I>0)

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.

Answer 2

#include<stdio.h>	
int main()
{					//因式分解
	int n,e=1,i=3;
	scanf("%d",&n);
	if(n<=1)
	{
	    printf("Error.\n");
	    goto v;
	}
	printf("%d=",n);
	for(;n%2==0;)
	{
		if(e) printf("%d",2);
		else printf("*%d",2);
		n/=2;
		e=0;
	}
	for(;n>=2;i+=2)
		for(;n%i==0;)
		{
			if(e) printf("%d",i);
			else printf("*%d",i);
			n/=i;
			e=0;
		}
	v: 
	return 0; 
}

Answer 3

太难了。。。能不能想办法先计算出20的质因数乘积模式，也即是20=2*2*2*5，然后这四个数的全排列去掉不重复的就是4种

追问

我一开始也这么想的，然后发现我tm的在数学层面上也不会做。。。囧
还是谢谢了啊

Answer 4

给你个思路吧，首先，任何数可以表示为：x＝p1^N1 × p2^N2 ×……pi^Ni，其中pi 是质数，
因此，你可以如下递归，当然，具体怎么做还是希望你自己实现，自己动手理解更深刻嘛。
//建立一个足够大的质数库
const int MAXP = 31622;
const int PCOUNT = 3401;
int prim[PCOUNT];
int max, numb;
void primes()
{
bool get[MAXP+1];
int i;
for(i = 0;i <= PCOUNT;i++) prim[i] = 0;
for(i = 2;i <= MAXP;i++) get[i] = true;
for(i = 2;i <= MAXP;i++)
if (get[i])
{
int j = i+i;
while(j <= MAXP){get[j] = false;j += i;}
}
for (int ii = 2,j = 0;ii <= MAXP;ii++)
if(get[ii]) prim[++j] = ii;
}

递归函数(当前递归起始质数index，上一级递归数字n)
{
for (int i=index;i<质数库数量;i++)
{
if (x == n*prim(index))//说明找到一种分解
{
print
return;
}
else(x < n*prim(index))//找过了，退回去
{
return;
}
else
{
下一级递归...
}
}
}
有问题欢迎追问，满意请采纳