P76048 偶数拆成质数 — 题解

专题： 函数
适用题目： 新生 OJ 本地题包中的 P76048，不要直接用于外站同名题。

解题思路

封装 is_prime()，从小到大枚举第一个质数 p，只要 e-p 也为质数就找到所需拆法。

复杂度

直接试除法最坏约 $O(n^2\sqrt n)$，数据规模允许。

易错点

按题意选择最小的 p，每个偶数只输出一行。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int is_prime(int x){
    if(x<2)return 0;
    for(int d=2;d*d<=x;d++)if(x%d==0)return 0;
    return 1;
}
int main(void) {
    int n;scanf("%d",&n);
    for(int e=4;e<=n;e+=2){
        for(int p=2;p<e;p++)if(is_prime(p)&&is_prime(e-p)){
            printf("%d=%d+%d\n",e,p,e-p);break;
        }
    }
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int d = 2; d * d <= x; d++) if (x % d == 0) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int e = 4; e <= n; e += 2) {
        for (int p = 2; p < e; p++) {
            if (is_prime(p) && is_prime(e - p)) {
                cout << e << '=' << p << '+' << e - p << '\n';
                break;
            }
        }
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。