质数和，虽然不是很容易

Question

给定一个数n和整数k，检查 k 个素数的和是否为n。

input 13 2
output: yes
explanation: 11+2 equals 13

由于 k 被假定为任何一般整数，我不知道如何解决它。我想通过创建所有质数的集合并寻找 k 数来解决它，但即使 k 小到 5，我们也必须运行 4 到 5 次循环才能做到这一点。如何解决此类问题，请寻求帮助，谢谢。我尝试初始代码为：

#include<iostream>
#include<unordered_set>
#include<vector>
using namespace std;
bool is_prime(int n){
    bool flag =true;
    for(int i=2;i<n;i++){
        if(n%i==0 && n!=i){
            flag=false;
            break;
        }
    }
    if(flag){
        return true;
    }
    return false;
}
int main(){
    int n;cin>>n;
    int k;cin>>k;
    unordered_set<int>s;
    for(int i=2;i<n;i++){
        if(is_prime(i)){
            s.insert(i);
        }
    }
}

Answer 1

这可以通过假设哥德巴赫猜想来解决。哥德巴赫猜想说：

任何偶数都是两个素数之和

我们可以利用它来创建以下规则：

1. 如果n < 2k那么 NO（因为 2 是最小的素数）
2. 如果k == 1那么 YES IFF n 是素数
3. If n >= 2kand k == 2THEN YES 如果 n 是偶数 (Goldbach) ，如果 n 是奇数则 NO iff n-2 不是素数
4. 如果n >= 2k和k >= 3那么总是是：
   • 当n是偶数时，它可以表示为2 + ... + 2 + (n - 2 * (k - 2))，
     n - 2 * (k - 2)也是偶数并且可以表示为两个素数的和（哥德巴赫）
   • 当n是奇数时，它可以表示为3 + 2 + ... + 2 + (n - 3 - 2 * (k - 3))，
     n - 3 - 2 * (k - 3)是偶数，并且可以通过两个素数（哥德巴赫）的总和来表示。