fac_bignum.c

计算大数阶乘

# include<stdio.h> 
# include <stdlib.h> 
// 计算 
# define N 1000
int  cal(unsigned int  *s,int  n) 
{ 

	unsigned long p; // p是对每一位乘法中的值加上进位，如34*5,4*5是20,3*5的加上进位2是17 
	unsigned long k=0; // k是一次乘法中的进位，如10进制乘法中，34*5,4*5的进位是2,3*5的进位是1 
	int  i; 
	static int  m=1; // m是位数，表示s有总共有多少位数字，注意：是1000进制 
	static int  b=0; 
	/* b用来记录后面的0，比如213,000,000,000，则b=3,后面的3个000不必再参与计算了 */ 
	// 
	for(i=b;i<m;i++) 
	{ 
		p=(long)s[i]*(long)n+k; 
		k=p/N; 
		s[i]=p-k*N; 
	} 
	// b是低位乘出来的000的数目,增加后加1 
	while(!s[b]) 
		b++; 
	// 最高位的进位处理 
	for(k=p/N;k;) 
	{ 
		p=k; 
		k=p/N; 
		s[i++]=p-k*N; 
		m++; // 进一次m加一次 
	} 

	return m; 
} 

void main() 
{ 
	/* s是用来存计算结果的，以N为进位，这里N=1000，如s[0]=1,s[1]=21,s[2]=213,s[3]以上都为0， 
	则结果是：213,021,001 
	*/ 
	unsigned int  *s; 
	int  i; 
	int  m; // m是位数，表示s有总共有多少位数字，注意：是1000进制 
	int  n; /* 求n! (0<n<10000)*/ 
	printf( "输入一个整数(0-10000):" );
	scanf("%d",&n); // 输入n的值 
	s=(unsigned int  *)malloc(n*sizeof(s)*10); // 数组开足够大，其实要不了这么大 
	// 附初值，S=1，即s[0]=1,以上都为0 
	for(i=1;i<n;i++) 
		s[i]=0; 
	s[0]=1; 
	
	// 循环，s乘以2、3、4,……,n 
	for(i=2;i<=n;i++) 
		m=cal(s,i); 
	// 输出：n!= 
	printf("\n%ld!=",n); 
	m=n-1; 

	// 滤掉前面的0,前面说了，其实 
	while(!s[m]) 
		m--; 
	// 输出第一位 
	printf("%ld",s[m--]); 
	// 输出后面的位数 
	for(i=m;i>=0;i--) 
		printf(",%03ld",s[i]); 
	printf("\n"); 
	// 释放内存空间 
	free(s); 
}