连续的素数之和改进版.txt

爱因斯坦的思考题 二叉树算法集 分解质因数新解 石子归并问题等有趣的C程序

 


/*某些正整数能够表示成一个或多个连续的素数之和,被给定的整数有多少个这样的表示形式呢? 例如,整数53
有两个这样的表示形式:5 + 7 + 11 + 13 + 17 和 53.整数41有三个:2+3+5+7+11+13, 11+13+17, 和 41.
整数3仅有一个:3.而整数20一个也没有.注意这些加数必须是连续的素数. 所以7 + 13 和 3 + 5 + 5 + 7 
都不是正确的表示整数20的形式, 你的任务是编一个程序输出给定的整数用此类形式表达的个数. 
Input 
输入一系列正整数,每行输入一个.输入的数要求在2-10 000(含10 000)间,最后输入一个0表示结束. 
Output 
输出是一列与所输入整数(最后一个0除外)对应的数,输出的数表示给定的整数用一个或多个连续的素数之和
表达的个数.无关的数据不要输出. 
Sample Input 

2
3
17
41
20
666
12
53
0

Sample Output 

1
1
2
3
0
0
1
2
*/

#include<stdio.h>
#include<stdlib.h>

#define N 10000

int Prime(int *prime);
int count(int n, int *p, int len);

int main(void)
{
    int i, m, n[N]={0}, len, sum=0, num[N]={0}, prime[N]={0}, *p=prime;
    
    len = Prime(p);//存储1-10000的所有素数
  do{   
     scanf("%d",&m);
     if(m<0 || m>10000)
      continue;
     if(m>0 && m<=10000)
      n[sum++] = m; //把输入的数据存入数组n[]   
  } while(m != 0);
  for(i=0; i<sum; i++)
  {  
   num[i] = count(n[i],prime,len);//累积元素num[i]的组合的个数
      printf("%d\n", num[i]);
   
  }
    
    system("pause");
    return 0;
}
int Prime(int *prime)
{
 int n, i, flag, sum=0;
 
 for(n=2; n<=N; n++)
 {
  flag = 0;
  for(i=2; i<=n/2; i++)//判断n是否为素数
  {
   if(n%i == 0)
   {
    flag = 1;
    break;
   } 
  }
  if(flag == 0)//若是则将其存入数组
  {
   prime[sum++] = n;
  }
 }

   return sum;
}

int count(int n, int *p, int len)
{
 int i, j, num, sum;
 
 num = i = 0;
 while((i<len)&&(p[i]<=n))  
 {
  sum = p[i];  //sum表示当前连续素数之和 ，给其赋初值p[i] 
  j = i;
  while((j<len)&&(sum<n))//当当前连续素数之和小于n时，累加连续素数 
   sum += p[++j];      
  if(sum == n)   //若这些素数之和等于n，num++ 
  {
   num++;
   j++;
  sum = p[i];     //跳过不可能的p[i]，以减少计算量 
  while(sum <= p[j])
   sum += p[++i];
    }
    else
     i++;
 }

 return num;
}