3132.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3132  User Id:fzk 
Memory:100K  Time:577MS
Language:C++  Result:Accepted

Source 

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

int ans[15][1200];
int prime[1200], pn;
bool sign[1200];

void init( ) {
	for( int i=2; i<1200; i++ )
		if( !sign[i] ) {
			for( int j=i+i; j<1200; j+=i )
				sign[j] = true;
		}
	pn = 0;
	for( i=2; i<1200; i++ )
		if( !sign[i] )
			prime[pn++] = i;
}

int main( ) {
	int i, j, n, k, l;
	
	init( );

	while( true ) {
		scanf( "%d%d", &n, &k );
		if( n == 0 && k == 0 )
			break;

		memset( ans, 0, sizeof ans );

		ans[0][0] = 1;
		for( i=0; i<pn; i++ )
			for( j=k-1; j>=0; j-- )
				for( l=0; l<=n-prime[i]; l++ )
					ans[j+1][l+prime[i]] += ans[j][l];
		printf( "%d\n", ans[k][n] );
	}
	return 0;
}