noi 7827 质数的和与积-白红宇

noi 7827 质数的和与积

阅读量：793 次

发布时间：2023-02-16

本文共 1221 字，大约阅读时间需要 4 分钟。

为了求解给定两个质数的和S，找出它们的最大乘积，我们可以采用以下步骤：

生成质数表：使用埃拉托斯特尼筛法生成所有不超过S的质数。

遍历质数对：从最小的质数p开始，计算q = S - p，并检查q是否为质数。

计算最大乘积：对于每对满足条件的质数(p, q)，计算它们的乘积，并记录最大的乘积。

以下是优化后的解决方案：

方法思路

质数生成：使用埃拉托斯特尼筛法生成所有不超过S的质数，存储在一个布尔数组中。

寻找质数对：遍历每个质数p，计算其补数q = S - p，检查q是否为质数。

计算乘积：对于每对有效的质数对(p, q)，计算它们的乘积，并更新最大乘积。

这种方法确保了在合理的时间内找到最大的乘积，适用于给定的约束条件。

解决代码

#include 
   
    #include 
    
     using namespace std;int main() {    int S;    cin >> S;        vector
     
       prime(S + 1, true);    prime[0] = prime[1] = false;    for (int i = 2; i * i <= S; ++i) {        if (prime[i]) {            for (int j = i * i; j <= S; j += i) {                prime[j] = false;            }        }    }        int max_product = 0;    for (int p = 2; p <= S / 2; ++p) {        if (prime[p]) {            int q = S - p;            if (q >= 2 && prime[q]) {                int product = p * q;                if (product > max_product) {                    max_product = product;                }            }        }    }        cout << max_product << endl;    return 0;}