Prime number sum ,Though not really easy

Question

Given a number n and integer k, check whether k prime number sums to n or not.

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

since k is assumed to be any general integer, I don't know how to solve it. I thought to solve it by creating set of all prime number and looking for k number but even if k is as small as 5 we have to run 4 to 5 loop to do it. how to approach such problem, kindly looking for help,thanks. I tried initial code as:

#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);
        }
    }
}

@jarod42 nothing was mentioned, consider integer range in general — def __init__
– def __init__, Commented Aug 5, 2021 at 11:22
So brute-force, or even O(N+K) seems out of consideration. Have to find a mathematical formula. — Jarod42
– Jarod42, Commented Aug 5, 2021 at 12:11

Jarod42 · Accepted Answer · 2021-08-05 12:35:28Z

6

This can be solved by assuming Goldbach's conjecture. Goldbach's conjecture says:

Any even integer is the sum of two prime numbers

We can exploit this to create the following rules:

If n < 2k then NO (because 2 is the smallest prime)
If k == 1 then YES IFF n is prime
If n >= 2k and k == 2 THEN YES if n is even (Goldbach) , If n is odd then NO iff n-2 is not a prime number
If n >= 2k and k >= 3 THEN Always YES:
- When n is even, it can be expressed as 2 + ... + 2 + (n - 2 * (k - 2)),
  n - 2 * (k - 2) is also even and can be expressed as a sum of two primes (by Goldbach),
- When n is odd, it can be expresses as 3 + 2 + ... + 2 + (n - 3 - 2 * (k - 3)),
  n - 3 - 2 * (k - 3) is even and can be expressed by sum of two primes (Goldbach).

edited Aug 5, 2021 at 12:35

Jarod42

227k15 gold badges214 silver badges349 bronze badges

answered Aug 5, 2021 at 11:30

Christian Sloper

7,5303 gold badges17 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Kitswas Over a year ago

Goldbach's conjecture is still a conjecture because it is yet to be proven. Creating an algorithm based on it might not be a wise move even if the verified results are sufficient for the purpose.

Brett Hale Over a year ago

@PalLaden - Well, if the algorithm fails, the OP has just found a counter-example to the Goldbach conjecture. That's a $1M prize or two right there. There's really no down-side.

armagedescu Over a year ago

@PalLaden it is proven for all integers less than 4×10^18, so for practical purposes it can be considered proven because that range is 10^9 larger than the range of C++ int

def __init__ Over a year ago

@christian sloper your approach seems visionary and you deduced it in a couple of minutes as well, It made me wonder, Thank you for the answer.

xskxzr Over a year ago

@BrettHale The problem is, the OP doesn't know the algorithm fails when it actually fails...

Collectives™ on Stack Overflow

Prime number sum ,Though not really easy

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related