HDU2098 分拆素数和【水题】【筛法求素数】

本文主要是介绍HDU2098 分拆素数和【水题】【筛法求素数】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
把一个偶数拆成两个不同素数的和，有几种拆法呢？
 
Input
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。
 
Output
对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。
 
Sample Input
30
26
0
 
Sample Output
3
2
 
Source

2007省赛集训队练习赛（2）

思路：用筛法求素数求出10000以内的素数，遍历2~N/2，直接判断i和N-i是否都为素数，

并且i和N-1不相等。如果满足条件，则总数加1。最终得到结果。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int Prime[10010];void IsPrime()
{for(int i = 2; i <= 10000; ++i)Prime[i] = 1;for(int i = 2; i <= 10000; ++i){if(Prime[i])for(int j = i+i; j <= 10000; j+=i)Prime[j] = 0;}
}int main()
{int N;IsPrime();while(cin >> N && N){int Count = 0;for(int i = 2; i <= N/2; ++i)if(Prime[i]==1 && Prime[N-i]==1 && i != N-i)Count++;cout << Count << endl;}return 0;
}

这篇关于HDU2098 分拆素数和【水题】【筛法求素数】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---