# 2877. 歌德巴赫猜想

C语言（C班）E题题解：

#include <stdio.h>
#include <math.h>
int isprime(int x)//判断质数基本算法
{
int i;
if(x==2) return 1;
for(i=3; i<(int)(sqrt(x)+1); i+=2)
if(x%i==0) return 0;
return 1;
}
int main()
{
int n, a, b;
while(scanf("%d",&n)!=EOF)
{
int i=n/2;
if(i%2==0) i--;//从奇数开始，可以避免判断偶数（n大于4，不可能存在偶数答案）
for(i; i>1; i-=2)//循环步长为2
if(isprime(i) && isprime(n-i)) break;//遇到符合条件的数直接跳出循环
printf("%d %d\n",i,n-i);
}
return 0;
}


def isPrime(n):
if n <= 1:
return False
if n == 2:
return True
elif n % 2 == 0:
return False
elif n == 3:
return True
elif n >=5:
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
else:
return True
while True:
try:
n = int(input())
j = n // 2
while j >=3:
if isPrime(j) == 1 and isPrime(n - j) == 1 :
a = j
b = n - j
break
j = j - 1
print(a,b)
except:
break

primes 1 20000 | gawk 'BEGIN{ printf "bool isprime[] = {"; i = 0}
{
while ( i < \$1)
{
printf "0, "
i++
}
printf "1, "
i++
}
END{
while ( i < 20000)
{
printf "0, "
i++
}
printf "0};\n"
}' >> eoj2877.cpp


PS: 代码能在OJ上过但是发到讨论里就炸了233333.

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

bool isprime[] = {......}

int main()
{
#ifdef debug
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif

int n;
while(scanf("%d", &n) > 0)
{
int i = n / 2; int j = n / 2;
while( i > 0 && j < n)
{
if(isprime[i] && isprime[j] && i + j == n)
{
printf("%d %d\n", i, j);
break;
}
i--;
j++;
}
}
return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 20000
int primes[N];
int prime_cnt = 0;

void fill_primes(){
memset(primes, 0, N * sizeof(int));
primes[0] = 2;
int next_i = 1;

for (int a = 3; a < N; a++){
int is_prime = 1;
for (int i = 0; (primes[i] != 0) && (primes[i] <= ceil(sqrt(a))); i++){
if (a % primes[i] == 0) {
is_prime = 0;
break;
}
}
if (is_prime) primes[next_i++] = a;
}
prime_cnt = next_i;
}

int get_floor_prime_index(int prime){
int left = 0;
int right = prime_cnt - 1;

while (left < right){
int mid = (left + right) / 2;
if (prime == primes[left])  return left;
if (prime == primes[mid])   return mid;
if (prime == primes[right]) return right;
if (left == right - 1)      return left;
if (prime > primes[mid]) {
left = mid;
} else {
right = mid;
}
}
}

int main(){
int n;
fill_primes();

while (scanf("%d", &n) > 0){
int floor_prime_index = get_floor_prime_index(n / 2);
int floor_prime = primes[floor_prime_index];

if (floor_prime == n / 2) {
printf("%d %d\n", floor_prime, floor_prime);
} else {
int left = floor_prime_index;
int right = left + 1;

int sum;
while ((sum = primes[left] + primes[right]) != n){
if (sum > n) left--;
if (sum < n) right++;
}
printf("%d %d\n", primes[left], primes[right]);
}
}

return 0;
}


int isprime(int num)
{
if(num<=3)
return num > 1;
if (num%6!=1&&num%6!=5)
return 0;
int sqrtnum=(int)sqrt(num);
for(int i=5;i<=sqrtnum;i+=6)
if (num%i==0||num%(i+2)==0)
return 0;
return 1;
}