/*某些正整數能夠表示成一個或多個連續的素數之和,被給定的整數有多少個這樣的表示形式呢? 例如,整數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;
}