You are given a number N. You need to check if it can be written as a

1.	You are given a number N. You need to check if it can be written as a sum of k prime numbers.
Answer» For example, Input : N = 5, k = 2 Output : True EXPLANATION : 10 can be written as 5 + 5 Input : N = 2, k = 2 Output : False Approach: We use the Goldbach Conjecture for solving this PROBLEM. Goldbach’s conjecture states that every even integer (greater than 2) can be represented as the sum of two primes. When N >= 2k and k = 1: The answer will be True if and only if N is a prime number When N >= 2K and K = 2: If N is an even number the answer will be Yes(Goldbach’s conjecture) If N is odd the answer will be No if N-2 is not a prime number and Yes if N-2 is a prime number. This is because we know odd + odd = even and even + odd = odd. So when N is odd, and K = 2 one number must be 2 as it is the only even prime number so now the answer depends on whether N-2 is odd or not. When N >= 2K and K >= 3: The answer will always be True. This is because when N is even N – 2(K-2) is also, even so, N – 2(K – 2) can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K – 2 times, p, q. When N is odd N – 3 -2(K – 3) is even so it can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K-3 times, 3, p, q // FUNCTION to check if a number is primebool checkPrime(int x){ for (int i = 2; i i <= x; i++) if (x % i == 0) return false; return true;}bool checkSumOfKPrimes(int N, int k){ // We return false if N < 2k if (N < 2k) return false; // If k = 1 we check if N is prime or not if (k == 1) return checkPrime(N); if (k == 2) { // if N is even the answer is true; if (N % 2 == 0) return true; // If N is odd, we check if N - 2 is prime or not return checkPrime(N - 2); } // If k >= 3, we return true; return true;} Explanation: In the above CODE, we created a function checkPrime which takes one input PARAMETER and we check if the given input is a prime number or not. We also created a function checkSumOfKPrimes which takes two input parameters N and k. In the function, we check if N can be represented as a sum of k prime numbers using the conditions of the Goldman Conjecture.

You are given a number N. You need to check if it can be written as a sum of k prime numbers.

Answer»

For example,
Input :
N = 5, k = 2

Output :
True

EXPLANATION :
10 can be written as 5 + 5

Input :
N = 2, k = 2

Output :
False

Approach:

We use the Goldbach Conjecture for solving this PROBLEM. Goldbach’s conjecture states that every even integer (greater than 2) can be represented as the sum of two primes.

When N >= 2k and k = 1:

The answer will be True if and only if N is a prime number

When N >= 2K and K = 2:

If N is an even number the answer will be Yes(Goldbach’s conjecture)

If N is odd the answer will be No if N-2 is not a prime number and Yes if N-2 is a prime number.

This is because we know odd + odd = even and even + odd = odd. So when N is odd, and K = 2 one number must be 2 as it is the only even prime number so now the answer depends on whether N-2 is odd or not.

When N >= 2K and K >= 3:

The answer will always be True. This is because when N is even N – 2*(K-2) is also, even so, N – 2*(K – 2) can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K – 2 times, p, q.

When N is odd N – 3 -2*(K – 3) is even so it can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K-3 times, 3, p, q

// FUNCTION to check if a number is primebool checkPrime(int x){ for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true;}bool checkSumOfKPrimes(int N, int k){ // We return false if N < 2*k if (N < 2*k) return false; // If k = 1 we check if N is prime or not if (k == 1) return checkPrime(N); if (k == 2) { // if N is even the answer is true; if (N % 2 == 0) return true; // If N is odd, we check if N - 2 is prime or not return checkPrime(N - 2); } // If k >= 3, we return true; return true;}

Explanation:

In the above CODE, we created a function checkPrime which takes one input PARAMETER and we check if the given input is a prime number or not. We also created a function checkSumOfKPrimes which takes two input parameters N and k. In the function, we check if N can be represented as a sum of k prime numbers using the conditions of the Goldman Conjecture.

You are given a number N. You need to check if it can be written as a sum of k prime numbers.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment