信息学奥赛一本通 1405：质数的和与积 （思维题）

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

【题目描述】

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

【输入】

一个不大于10000的正整数S，为两个质数的和。

【输出】

一个整数，为两个质数的最大乘积。数据保证有解。

【输入样例】

50

【输出样例】

589

思路：

一个数拆成两部分，如何乘积最大，例如：50拆成1和49以及50拆成25和25，显然这两个数越靠近中间，乘积越大，题目有个坑就是这两个质数可以是一样的，但是题目没有说明。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

bool flag = false;

bool isprime(int x) {
    if(x == 1) return false;
    for(int i = 2; i <= x / i; i ++) {
        if(x % i == 0) return false;
    }
        return true;
}

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

    int x;
    cin >> x;

    int h = x / 2;
    for(int i = h; i <= x; i ++) {
        for(int j = i; j >= 0; j --) {
            if(isprime(i)  && isprime(j) && i + j == x) {
                cout << i * j;
                flag = true;
                break;
            }
        }
        if(flag) break;
    }

    return 0;
}