质数的和与积

题目描述

给定一个不大于 $10000$ 的正整数 $S$ ，求满足 $p+q=S$ 且 $p,q$ 均为质数的分解中，乘积 $p \cdot q$ 的最大值。数据保证有解。

思路

用埃氏筛预处理 $2 \sim S$ 的质数表，然后从 $p=\lfloor S/2 \rfloor$ 开始向下枚举。 $p$ 与 $S-p$ 都是质数的第一个 $p$ 对应的乘积 $p(S-p)$ 就是最大值，因为两数之和固定时越接近乘积越大。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# 质数的和与积：两个质数和为 S，求最大乘积
# 埃氏筛预处理 <=S 的质数表，从 p=S//2 向下枚举：p 与 S-p 均为质数的首个 p 即最优
# 因为 p*(S-p) 关于 S/2 对称且随 p 靠近 S/2 增大

import sys

data = iter(map(int, sys.stdin.buffer.read().split()))
S: int = next(data)  # 两个质数的和
is_comp: list[bool] = [False] * (S + 1)  # 埃氏筛标记合数
for i in range(2, int(S**0.5) + 1):
    if not is_comp[i]:
        is_comp[i * i :: i] = [True] * len(is_comp[i * i :: i])

p = next(p for p in range(S // 2, 1, -1) if not is_comp[p] and not is_comp[S - p])
print(p * (S - p))

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:02
 * update_at: 2026-10-05 23:02
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXS = 10005;

bool is_comp[MAXS]; // is_comp[x] = true 表示 x 是合数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S;
    if (!(cin >> S)) return 0;

    // 埃氏筛标记合数
    for (int i = 2; i * i <= S; ++i) {
        if (!is_comp[i]) {
            for (int j = i * i; j <= S; j += i) {
                is_comp[j] = true;
            }
        }
    }

    // 从 S/2 向下枚举较小质数 p，首个满足 p 与 S-p 均为质数的即最优
    int ans = 0;
    for (int p = S / 2; p >= 2; --p) {
        if (!is_comp[p] && !is_comp[S - p]) {
            ans = p * (S - p);
            break;
        }
    }

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码