首页 > 代码库 > 分拆素数和 埃氏筛法
分拆素数和 埃氏筛法
分拆素数和
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
HDU 2098
Description
把一个偶数拆成两个不同素数的和,有几种拆法呢?
Input
输入包含一些正的偶数,其值不会超过10000,个数不会超过500,若遇0,则结束。
Output
对应每个偶数,输出其拆成不同素数的个数,每个结果占一行。
Sample Input
30
26
0
Sample Output
3
2
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
HDU 2098
Description
把一个偶数拆成两个不同素数的和,有几种拆法呢?
Input
输入包含一些正的偶数,其值不会超过10000,个数不会超过500,若遇0,则结束。
Output
对应每个偶数,输出其拆成不同素数的个数,每个结果占一行。
Sample Input
30
26
0
Sample Output
3
2
#include <iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<deque> #define MAX 10007 using namespace std; int n,ans; bool isprime[10007]; void sieve() { int p=0; for(int i=0;i<MAX;i++) isprime[i]=true; isprime[0]=isprime[1]=false; for(int i=2;i<MAX;i++) { if(isprime[i]){ for(int j=2*i;j<MAX;j+=i) isprime[j]=false; } } } int main() { while(1){ ans=0; scanf("%d",&n); if(n==0) break; sieve(); for(int i=2;i<n/2;i++) { if(isprime[i]&&isprime[n-i]) ans++; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。