c语言1000以内的质数（C语言标准分解质因数）

//分解质因数程序：把区间[m,n]的整数分解为标准形式(其中m,n为自然数且1<=m<=n<2^31)

#include <stdio.h> /*包含输入输出函数*/

#include <math.h> /*包含数学函数*/

int main () /*主函数*/

{ int z[4793]={2}; //因小于2^31的平方根的素数有4392个

int i,x,g=1,b,q,m,n; //循环变量i,数组下标x,素数个数g,被分解数b,平方根q,范围[m,n]

for(i=3;i<=46349;i =2) //因46349^2已经大于2^31

{ x=0;q=sqrt(i); //每次都从z[0]开始检验

while (i%z[x]!=0) //如i不能被z[x]整除时一直检验

{ if(z[x]<=q) x ; //不能确定是素数时：用数组中的下一个素数检验

else //确定是素数时：

{ z[g]=i;g ; //保存该素数，素数总个数加1，

break; //退出内循环：检验下一个i

}

}

}

printf("请输入要分解的整数范围m n(用空格隔开)：");scanf("%d %d",&m,&n);

for(i=m;i<=n;i )

{ printf("\n%d=1",i);

x=0;b=i; //每次都从z[0]起检验；把i先给被除数b

while(b>1) //没有分解完继续

{ g=0;q=sqrt(b); //相同因数个数g置0；

if(z[x]>q){printf("*%d",b);break;} //把i分解完了退出，分解下一个数

while (b%z[x]==0){g ;b/=z[x];} //反复用z[x]去除，并累计能整除的次数 ,直到不能整除

if(g>0)printf("*%d",z[x]); //z[x]是p的因数时，打印z[x]

if(g>1)printf("^%d",g); //相同因数多于一个时，打印因数个数

x ; //用下一个素数检验

}

}

return 0;

}