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<stdio.h>
#include<math.h>
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<i) printf("%ld\n",b); /*输出大于i平方根的因数*/
if(b==i){printf("(素数!)\n");w++;} /* b=i,表示i无质因数*/
}
printf("其中共%d个素数.\n",w);
}
程序运行结果如下：
责任编辑：cyth
