2909.txt

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

Problem Id:2909  User Id:fzk 
Memory:104K  Time:0MS
Language:C++  Result:Accepted

Source 

//#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

int prime[30000];
int pnum = 0;
bool sign[1<<16]= { 0 };

void init() {
	int i, j;
	for( i=2; i<=(1<<15); i++ ) {
		if( !sign[i] ) {
			for( j= i+i; j<=(1<<15); j+=i )
				sign[j] = true;
			prime[pnum++] = i;
		}
	}
}

int main( ) {
	int a, c, i, j;
	init( );
	while( 1 ) {
		scanf( "%d", &a );
		if( !a ) break;
		c = 0;
		for( i=0, j=pnum-1; i<=j; i++ ) {
			while( j>i && prime[j]+prime[i] > a )
				j--;
			if( prime[j]+prime[i] == a )
				c++;
		}
		printf( "%d\n", c );
	}
	return 0;
}