首页 > 代码库 > Bestcoder round 18---A题(素数筛+素数打表+找三个素数其和==n)
Bestcoder round 18---A题(素数筛+素数打表+找三个素数其和==n)
Primes Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12 Accepted Submission(s): 11
Problem Description
Given a number n, please count how many tuple(p1, p2, p3) satisfied that p1<=p2<=p3, p1,p2,p3 are primes and p1 + p2 + p3 = n.
Input
Multiple test cases(less than 100), for each test case, the only line indicates the positive integer n(n≤10000).
Output
For each test case, print the number of ways.
Sample Input
39
Sample Output
02
代码:
#include <string>#include <iostream>#include <cstdio>#include <math.h>#include <cstring>#include <algorithm>#include <queue>using namespace std;int f[10001];void sushu(){ int i, j; memset(f, 0, sizeof(f)); f[1]=1; i=2; while(i<=200) { for(j=i*2; j<=10000; j+=i) { f[j]=1; } i++; while(f[i]==1) { i++; } }}int s[10000], e;int main(){ int n; int i, j, k; int cnt; sushu(); e=0; for(i=2; i<=10000; i++) { if(f[i]==0) { s[e++]=i; } } while(scanf("%d", &n)!=EOF) { if(n<6) { cout<<‘0‘<<endl; continue; } cnt=0; for(i=0; i<=n; i++) { for(j=i; j<=n; j++) { for(k=j; k<=n; k++) { if((s[i]+s[j]+s[k])==n) { cnt++; } } } } cout<<cnt<<endl; } return 0;}
Bestcoder round 18---A题(素数筛+素数打表+找三个素数其和==n)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。