Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 水过，0ms

Posted by KatrineYang at 2016-07-18 16:35:59 on Problem 2909
```//============================================================================
// Name        : Goldbach.cpp
// Author      :
// Version     :
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

bool isPrime[32770] = {false};

int primelist[42] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181};

bool isprime(int n){
int sqrtn = (int)sqrt(n*1.0);
bool prime = true;
for(int i = 3; i <= sqrtn; i += 2){
if(n%i == 0){
prime = false;
break;
}
}
return prime;
}

int geshu[32770] = {0};

int main() {

for(int i = 0; i < 42; i++){
isPrime[primelist[i]] = true;
}
//int cn = 0;
for(int i = 183; i <= 32767; i += 2){
bool res = true;
int sqrti = (int)sqrt(i*1.0);
for(int j = 1; j < 42; j++){
if(primelist[j] > sqrti + 1) break;
//cn ++;
if(i%primelist[j] == 0){
res = false;
break;
}
}
isPrime[i] = res;
}
//cout << cn << endl;
int N;

//cout << endl;
while(1){
scanf("%d", &N);
if(N == 0) return N;
if(geshu[N] != 0){
//cout << geshu[N] << endl;
printf("%d\n", geshu[N]);
continue;
}
if(N%2 == 1){
if(isPrime[N-2]) printf("1\n");
else printf("0\n");
continue;
}
int cnt = 0;
for(int i = 2; i <= N/2; i++){
if(isPrime[i] && isPrime[N-i]){
cnt ++;
}
}
geshu[N] = cnt;
printf("%d\n", cnt);
}
return 0;
}
```

Followed by: