POJ2262

テーマLINK
題意解釈
2つの質量数を探して、彼らは与えられた1つの数に等しく加算して、同時にこの2つの数の差が最大であることを保証します.(題意がよく理解されている)この問題の重点は時間制限にあり,質数を判定する際には最も簡単な方法ではなく,質数フィルタリング法を用いるべきである.同時に表を打った後、別の質量数を探すときは二分法を使って探したほうがいいです.結果はACになります.
収穫する
コードテクニック

lower_bound()これはalgorithmのヘッダファイルで、とても使いやすく、二分法で検索します.

初期化の時、defineで来たほうがいいです.私は9を少なくして午前中の間違いを調べました.

ACコード

#include 
#include 
#include 

using namespace std;

#define MAXN 1000010
#define ll long long

int Prime[MAXN];
bool NotPrime[MAXN];
int prime_total;


void generate_prime(int n){
    //prime_total = 0;
    for(ll i = 2; i <= n; i++){
        if(!NotPrime[i]){
            Prime[prime_total++] = i;
            for(ll j = i*i; j <=n; j+=i){
                NotPrime[j]=true;
            }
        }
    }
}

void solve(int number){
    for(int i = 0; i < prime_total;i++){
        int a = Prime[i];
        int b = *lower_bound(Prime,Prime+prime_total,number-a);
        if(a+b==number){
            cout << number << " = " << a << " + " << b << endl;
            break;
        }
    }
    return ;
}

int main()
{
    int num;
    generate_prime(999999);
    cin >> num;
    while(num != 0){
        solve(num);
        cin >> num;
    }
    return 0;
}