题解 B2134 【质数的和与积】
BotDand
·
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 时呢？
不妨加一个因子 $3$，即可分为两组：$1,3$ 和 $3,9$，问题解决。
即可打出代码：
```cpp
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
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< return 0; }