2877. 歌德巴赫猜想

#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;
}

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 

#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;
}