1105: 歌德巴赫猜想

Question

1105: 歌德巴赫猜想

题目描述
任一个大于等于4的偶数都可以拆分为两个素数之和。

（5.1.40）

输入
一个整数n( 4 <= n <= 200 ）
输出
将小于等于n的偶数拆分为2个质数之和，列出所有方案
样例输入
10
样例输出
4=2+2
6=3+3
8=3+5
10=3+7
10=5+5

Answer 1

这是一个求解哥德巴赫猜想的问题，需要找出所有小于等于给定数字n的偶数，并将这些偶数拆分为两个质数的和。

我们可以使用双指针法来解决这个问题。具体来说，我们可以遍历所有的素数对，并在遍历过程中检查当前的素数对之和是否等于当前的偶数。如果是，那么就将该偶数和对应的素数对加入结果集。

以下是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

void goldbach(int n) {
    vector<int> primes;
    for (int i = 2; i <= n / 2; i++) {
        if (isPrime(i) && isPrime(n - i)) primes.push_back(i);
    }
    for (int i = 0; i < primes.size(); i++) {
        cout << n << "=" << primes[i] << "+" << n - primes[i] << endl;
    }
}

int main() {
    int n;
    cin >> n;
    goldbach(n);
    return 0;
}

在上述代码中，我们首先定义了一个isPrime函数来判断一个数是否是质数。然后我们遍历2到n/2的所有整数，并检查它们是否是质数。如果是，就将它们加入primes数组中。接着，我们遍历primes数组中的所有元素，并将当前元素和n减去当前元素的结果输出。这样就可以得到所有小于等于n的偶数的所有质数对拆分方案。