[原创]NKOJ数分解递归实现
题目描述:把一个给定的整数分解成若干个素数的和。
Input
一个数。(32位无符号整型数范围内。)
Output
一些素数。
Sample Input
9Sample Output
3 3 3
实现:
#include<stdio.h>
#include<math.h>
int prime(unsigned int n) //素数判断
{
unsigned int i;
int flag=0; //标志位设为0
for(i=2;i<=sqrt(double(n))+1;i++)
{
if(n==2) { flag=1; break; }
if(n%i!=0) flag=1;
else { flag=0; break; }
}
if(flag==1) return 1;
if(flag==0) return 0;
}
void serparte(unsigned int n,int k,int i) //分解数
{
if(n%i==0||prime(n))
{
k=n-i;
printf("%d ",i);
if(prime(k)) printf("%d ",k);
else
serparte(k,k,i);
}
else
{
++i;
serparte(n,k,i);
}
}
int main()
{
int n,k=0;
while(scanf("%d",&n)!=EOF)
serparte(n,k,2);
return 0;
}