训练1-J

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

Input

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

Output

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

Sample Input

Sample Output

3

2

思路：首先用筛法将素数标记，不清楚筛法的可以看我另一篇文章筛法求素数

然后判断满足条件的个数，因为a[i]=i,所以a[i]+a[n-i]=i+n-i=n;

所以只要判断a[i]和a[n-i]是不是同时为素数就行了。代码有点乱，懒得改了

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

int main()

{

		int i, j, a[10000], n;

	a[0] = 0; a[1] = 0;

	for (i = 2; i < 10000; i++)

		a[i] = 1;            //从2开始初值赋1，相当于true

	for (i = 2; i < 10000; i++)

	{

		if (a[i])

			for (j = i * 2; j < 10000; j += i)

				a[j] = 0;    //标记置0

	}

	int count;

			while(cin>>n)

		{

			if(!n)

			return 0;

			count=0;

			for(int i=3;i<n/2;i++){

			if(a[i]&&a[n-i])

			  count++;

			}

			printf("%d\n",count);

		}

	return 0;

}

巴特西

训练1-J

最新文章

热门文章