[原创]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;
}

在来个非递归的:
#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 i;
    for(i=2;;)
    {
        if(n%i==0||prime(n))
        {
            n=n-i;
            printf("%d ",i);
            if(prime(n))
            {
                printf("%d ",n);
                break;
            }
            else continue;
        }
        else
        {    ++i;  }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
        serparte(n);
    return 0;
}
时间还是慢~

没有考虑 9 = 7 + 2 或者 5 + 2 + 2 等情况？

把一个给定的整数分解成若干个素数的和。

如果可以我直接给分成若干个2和1/0个3.

回复 4# 的帖子

其实应该说若干个 2 和 0/1 个 3/5/7/11/…

是啊，题目有点松了，要说分解成最少个素数还凑合。

完全不需要3后面的数.

呵呵，对了,,,谢谢nuciewth的提醒......从5开始都可以被2,3分解了/////

回复 8# 的帖子

是从2开始

1是不是素数好像又争议~