3113153_ac_30ms_228k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <math.h>
#include <stdio.h>
#include <string.h>

int cnt[1121][15];
int prime[200], num;

int isprime(int n)
{
	int i, q;

	q = (int)sqrt(n);
	for (i = 3; i <= q; i += 2)
	{
		if (n%i==0)
		{
			return 0;
		}
	}
	return 1;
}

void init()
{
	int i;
	
	prime[0] = 2;
	num = 1;
	for (i = 3; i < 1120; i += 2)
	{
		if (isprime(i))
		{
			prime[num++] = i;
		}
	}
	memset(cnt,0,sizeof(cnt));
}

void dp()
{
	int i, j, k;
	
	cnt[0][0] = 1;
	for (i = 0; i < num; i++)
	{
		for (j = 1120-prime[i]; j >= 0; j--)
		{
			for (k = 13; k >= 0; k--)
			{
				cnt[j+prime[i]][k+1] += cnt[j][k];
			}
		}
	}
}

int main()
{
	int n, k;
	
	init();
	dp();
	while (scanf("%d%d",&n,&k)==2)
	{
		if (n==0&&k==0)
		{
			break;
		}
		printf("%d\n",cnt[n][k]);
	}
	return 0;
}