自动搬运

查看原文

来自洛谷，原作者为

	BotDand AFO

搬运于2025-08-24 21:07:35，当前版本为作者最后更新于2021-07-03 21:06:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Problems}$

两个质数的和是 $S$，它们的积最大是多少？

$\text{Answer}$

可以考虑先确定一个质数 $x$，则另一个质数为 $(S-x)$。

考虑如何判断质数。

首先要知道什么是质数。

质数是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。（摘自百度百科）

那么可以打出代码：

bool check(int n)
{
    for(int i=2;i<=n;++i)//从2枚举到n
        if(n%i==0)//如果有n的因数
          return false;//则不是质数
    return true;//是质数
}

但是这样的方法不够优，复杂度为$\Theta (S)$，会超时。

考虑优化复杂度。

当 $S=8$ 时，$S$ 的因子为 $1,2,4,8$，可将 $S$ 的因子分为两类，$1,2$ 和 $4,8$，不难看出前者小于 $\sqrt{S}$，后者大于 $\sqrt{S}$，而通过前者即可算出后者，所以只需枚举前者，而前者小于 $\sqrt{S}$，复杂度降为 $\Theta (\sqrt{S})$。（$\sqrt{S}$ 即为 $S$ 的根号，如 $\sqrt{2}$约为 $1.414$，$\sqrt{3}$ 约为 $1.732$）

但是当 $S=9$ 时呢？

$9$ 的因子为 $1,3,9$，怎么分配？

不妨加一个因子 $3$，即可分为两组：$1,3$ 和 $3,9$，问题解决。

即可打出代码：

bool check(int n)
{
    for(int i=2;i*i<=n;++i)//从2枚举到√n
        if(n%i==0)//如果有n的因数
          return false;//则不是质数
    return true;//是质数
}

最后枚举其中一个质数即可，时间复杂度 $\Theta (S\sqrt{S})$。

哦对还要特判 $S$ 是否为 $0$ 或 $1$，因为 $0,1$ 不是质数，但循环不会运行，会返回 $\texttt{True}$。

$\text{Code}$

#include<bits/stdc++.h>
using namespace std;
int S;
int ma;
bool check(int n)
{
    if(n<2) return false;//特判0，1
    for(int i=2;i*i<=n;++i)
        if(n%i==0)
            return false;
    return true;
}
int main()
{
    cin>>S;
    for(int i=1;i<=S;++i)
        if(check(i))
            if(check(S-i))
                if(i*(S-i)>ma)//找最大值
                    ma=i*(S-i);
    cout<<ma;
    return 0;
}