分拆素数和

分拆素数和

Problem Description

把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。

Output

对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

Sample Input

30

26

0

Sample Output

3

2 先将10000以内的所有素数存到数组中，以后每次用的时候从数组中取自己需要的个数，省去了每次都需要计算的麻烦；值得注意的是1不算素数，总体策略是从两头往中间挤

完整代码：

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;	
int main(){
	int m;
	int k;
	vector<int> a(1230,0);
	int s;
	int t;
	int j;
	int i=0;
	for(t=2;t<10000;t++){
		
		for(s=2;s<=sqrt(t);s++){
			if(t%s==0){
				break;
			}
		}
		if(s>sqrt(t)){	
			a[i]=t;
			i++;
		}
	}
	cin>>m;
	while(m){
		int p,q;
		int count=0;
		for(j=0;a[j]<m;j++)
		p=0;
		q=j-1;
		while(p<q){
			
			if(a[p]+a[q]>m)
				{q--;
				}
			else if(a[p]+a[q]<m)
				{
				p++;		}
			else{
				count++;
				p++;
				q--;
				
			}
		}
		cout<<count<<endl;
		cin>>m;
	}
}