C趣味程序(二)(08)分解质因数乘积形式

文章作者 100test 发表时间 2007:03:10 17:39:09
来源 100Test.Com百考试题网

2.2 分解质因数
2.2.1 分解质因数乘积形式
把指定区间上的所有整数分解质因数，每一整数表示为质因数从小到大顺序排列的乘积形式。如果被分解的数本身是素数，则予以注明。
例如，90=2*3*3*5，91=素数。
算法分析如下：
对每一个被分解的整数i，赋值给b(以保持判别运算过程中i不变)，用k(从2开始递增1取值)试商：
若不能整除，说明该数k不是b的因数,k增1后继续试商。若能整除，说明该数k是b的因数，打印出"*k"，b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1继续。
按上述从小到大试商确定的因数显然为质因数。
循环取值k的终值如何时确定，一定程度上决定了程序的效率。终值定为i-1或i/2，试商循环次数都比较大，无效循环太多。循环终值定为i的平方根sqrt(i)可大精简试商次数，此时对于大于sqrt(i)的因数(至多1个!)，在试商循环结束后要注意补上，不要遗失。
如果整个试商后b的值没有任何缩减，仍为原来的待分解数i，说明i是素数，作素数说明标记。
程序代码如下：
程序运行结果如下：
#include
#include
void main()
{
long int b,i,k,m,n,w=0.
printf("[m,n]中整数分解质因数.\n").
printf("请输入m,n:").
scanf("%ld,%ld",&.m,&.n).
for(i=m.i<=n.i ) /*i为待分解的整数*/
{
printf("%ld=",i).
b=i.k=2.
while(k<=sqrt(i)) /*k为试商因数*/
{
if(b%k==0)
{
b=b/k.
if(b>1){printf("%ld*",k).continue.} /*k为质因数，返回再试*/
if(b==1) printf("%ld\n",k).
}
k .
}
if(b>1&.&.b if(b==i){printf("(素数!)\n").w .} /* b=i,表示i无质因数*/
}
printf("其中共%d个素数.\n",w).

}
程序运行结果如下：