学步园

先打素数表，然后打表就OK了。水题一个。

/*

MDK

2739

Accepted

796K

0MS

G++

2305B

2011-11-03 21:45:41

*/

LL mat[MAXN];

bool is[MAXN];
int prm[MAXN];
int getprm(int n)
{
int i, j, k = 0;
int s, e = (int)(sqrt(0.0 + n) + 1);
        memset(is, 1, sizeof(is));
        prm[k++] = 2;
is[0] = is[1] = 0;
for (i = 4; i < n; i += 2) is[i] = 0;
for (i = 3; i < e; i += 2) if (is[i]) {
                        prm[k++] = i;
for (s = i * 2, j = i * i; j < n; j += s)
is[j] = 0;
// 因为j是奇数，所以+奇数i后是偶数，不必处理！
                }
for ( ; i < n; i += 2) if (is[i]) prm[k++] = i;
return k; // 返回素数的个数
}

void init()
{
        SET(mat,0);
int len = getprm(MAXN);
    LL sum;
    F(i,len) {
        sum =0;
for(int k = i;k < len;k++) {
            sum += prm[k];
if(sum > MAXN) break;
            mat[sum]++;
        }
    }
}



int main ()
{
        init();
int n;
while(~SCF(n) && n) {
                printf("%d\n",mat[n]);
        }
}