题解 B2134 【质数的和与积】

· · 题解

\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<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;
}