质数和分解问题

最新推荐文章于 2024-10-22 23:18:33 发布

oopos

最新推荐文章于 2024-10-22 23:18:33 发布

阅读量2.7k

点赞数

文章标签： math.h output system string input 编程

本文链接：https://blog.csdn.net/oopos/article/details/1829950

版权

/*
质数和分解（normal）

Time Limit:1000MS  Memory Limit:65536K
Total Submit:178 Accepted:66

Description

任何大于 1 的自然数 n，都可以写成若干个大于等于 2 ，且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式：
9 = 2+5+2 = 2+3+2+2 = 3+3+3 = 2+7 。
这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。
试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。

Input

（prime.in）文件中的每一行存放一个自然数 n , 2≤n≤200。

Output

（prime.out）依次输出每一个自然数 n 的本质不同的质数和表达式的数目。

Sample Input

2

Sample Output

1

*/
/*
说明：这个程序效率不高，哪位有更高的PM我一下，谢谢！！！发至：oopos@126.com
*/
#include < stdio.h >
#include < math.h >
#include < string .h >

#define MAX 201

int prime[MAX] = { 0 },lp = 0 ,total = 0 ;

void makeprime( void )
{
      int i,j ;
     prime[ ++ lp] = 2 ;
      for (i = 3 ; i <= MAX ; i ++ )
     {
              for (j = 2 ; j * j <= i ; j ++ )
              if (i % j == 0 )
              break ;
              if (j * j > i)
             prime[ ++ lp] = i ;

     }
}

int is_prime( int x)
{
     int y;
     for (y = 1 ; y <= lp ; y ++ )
     if (x == prime[y])
     return 1 ;
     return 0 ;
}

int is_ok( int * sum, int num)
{
     int i ;
     for (i = 1 ; i <= num ; i ++ )
     if ( ! is_prime(sum[i]))
     return 0 ;
     return 1 ;
}


void trytodo ( int * sum, int min, int max, int num)
{
      int p,q ;
      if (is_ok(sum,num)) /* 检查是否全为质数 */
     {
       total ++ ;
        /* for(q=1 ; q<= num ; q++)
       printf("%d ",sum[q]);
       printf(" "); */
     }

      for (p = min ; p <= max / 2 ; p ++ )
      if (is_prime(p))
     {
           sum[num + 1 ] = max - p ;
           sum[num] = p ;
           trytodo(sum,sum[num],sum[num + 1 ],num + 1 );
     }
}

int main( void )
{
     int h,k,n,sum[MAX] = { 0 };
    scanf( " %d " , & n);

    makeprime() ;
     if (is_prime(n))
    total ++ ;

     for (h = 2 ; h <= n / 2 ; h ++ )
    {
           if (is_prime(h)) /* 至少要分到一个质数,不然会重复，这也叫剪枝吧 */
          {
               sum[ 1 ] = h ;
               sum[ 2 ] = n - h;
               trytodo(sum,sum[ 1 ],sum[ 2 ], 2 ) ;
          }
    }

    printf( " total = %d " ,total);

     /* for(k=1 ; k<= lp ; k++) *//* 产生质数
    printf("%d ",prime[k]);
    printf(" lp=%d ",lp); */
    system( " pause " );
     return 0 ;
}