邢育森电影:使用递归结构进行素数分解
12. 使用递归结构进行素数分解
/*使用递归结构进行素数分解*/
#include
/*声明函数isprim(int num)判断一个数是否为素数*/
int isprim(int num);
/*声明函数max(int num)求一个数的最大为素数的公约数*/
int max(int num);
/*声明函数printprim(int num)打印素数分解的结果*/
int printprim(int num);
main()
{
/*from起始数,to结尾数,num被操作数*/
int from,to,num;
printf("输入判断范围(from,to):\n");
scanf("%d,%d",&from,&to);
printf("整数十到二十之间的素数分解为:");
/*从from到to逐一对数进行操作*/
for(num=from;num<=to;num++)
{
printf("\n%d=",num);
printprim(num);
}
printf("\n");
return(0);
}
/*定义函数isprim(int num)判断一个数是否为素数*/
int isprim(int num)
{
int p=1,i=2,r;
while(i
{
r=num%i;
if(r==0)
p=0;
else
i=i+1;
}
return p;
}
/*定义函数max(int num)求一个数的最大为素数的公约数*/
int max(int num)
{
int i;
i=num-1;
/*i从num-1开始递减,至i为素数且能整除num时结束循环*/
while((num%i!=0)||(isprim(i)==0))
{
i=i-1;
}
return i;
}
/*定义函数printprim(int num)打印素数分解的结果*/
int printprim(int num)
{
int n;
n=num;
if(max(num)!=1)
{
printf("%d*",max(num));
/*输入的值=前一个因子最大素公约数*/
return printprim(num/max(num))*max(num);
}
/*当所得因子为素数且能整除操作数时结束递归*/
if(isprim(num)==1&&n%num==0)
{
printf("%d",num);
return num;
}
}