【POJ】2262

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1000001;

int prime[N];
bool primeQ[N];
int x, cur, cnt;

int main(int argc, char const *argv[]){
    for (int i = 0; i < N; ++i)primeQ[i] = true;
    for (int i = 2; i < N; ++i){
        if(primeQ[i])prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= N; ++j){
            primeQ[i * prime[j]] = false;
            if(i % prime[j] == 0)break;
        }
    }
    scanf("%d", &x);
    while(x){
        printf("%d = ", x);
        cur = 0;
        while(!primeQ[x - prime[cur]]){
            cur++;
        }
        printf("%d + %d
", prime[cur], x - prime[cur]);
        scanf("%d", &x);
    }
    return 0;
}

Review

• 一开始暴力打了个素数表结果超出文件大小了，于是学习了线性筛
• 直接枚举素数然后检验差就可以了
• 水题。TLE还是经验不足了