Блог

Учитывая число 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 amp;amp; 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);
        }
    }
}
 

Это может быть решено, если принять гипотезу Гольдбаха. Гипотеза Гольдбаха гласит:

Любое четное целое число является суммой двух простых чисел

Мы можем использовать это для создания следующих правил:

1. Если n < 2k тогда НЕТ (потому что 2-наименьшее простое число)
2. Если k == 1 тогда ДА, если n является простым
3. Если n >= 2k и k == 2 ТОГДА ДА , если n четно (Гольдбах), если n нечетно, то НЕТ, если 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) является четным и может быть выражено суммой двух простых чисел (Гольдбах).