Last Updated: 30 Sep, 2021
Prime And Validity
Hard
Asked in company
A prime number is a number that has only two factors, 1 and the number itself. Ninja came across a problem in which he has a number ‘N’, and Ninja has to find whether ‘N’ can be formed with the sum of ‘K’ prime numbers.
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains 2 space-separated integers, representing the integers ‘N’ and ‘K’.
Output Format :
For each test case, print the 1, if the number can be formed with the sum of ‘K’ prime numbers, else print 0.
Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N, K <= 3*10^3
Time Limit: 1 sec
Approaches
The basic idea is to check for all the possible combinations of forming ‘N’ by the sum of ‘K’ prime numbers.
Here is the algorithm :
- Base case
- If ‘N’ is smaller than equal to 0, return 0.
- If ‘K’ is equal to 1, check if ‘N’ is a prime number or not.
- Run a loop from 2 to ‘N’ (say, iterator ‘i’), that can be used for forming ‘N’.
- Check if ‘i’ is a prime number.
- Call the function recursively by updating ‘N’ by ‘N’ - ‘i’ and ‘K’ by ‘K’ - 1 and check if the value returned by the recursive function is 1, return 1.
- Check if ‘i’ is a prime number.
- Finally, return 0.
isPrime(N)
- Run a loop from 2 to square root of ‘N’ (say, iterator ‘i’)
- Check if the ‘N’ is divisible by i
- Return FALSE.
- Return TRUE.
The idea is to use Goldbach’s Conjecture which states that every even integer greater than 2 can be expressed as the sum of two prime numbers.
Example:
44 = 41 + 3
38 = 31 + 7
There are three conditions we need to solve.
- If ‘N’ >= ‘2*K’ and ‘K’ = 1, if ‘N’ is a prime number then the result is 1 as the number itself is the sum.
- If ‘N’ >= ‘2*K’ and ‘K’ = 2, we can use Goldbach’s conjecture here. If ‘N’ is even, result if 1, or if ‘N’ is odd we simply need to check whether ‘N’ - 2 is a prime number or not.
- If ‘N’ >= ‘2*K’ and ‘K’ >= 3, then it is always 1. If ‘N’ is even, then ‘N’ - 2*(‘K’ - 2) will also be even and can be written as the sum of two prime numbers, ‘P’ and ‘Q’, using Goldbach’s Conjecture and can be written as 2, 2, …, ‘K’ - 2 times, ‘P’, ‘Q’. Similarly, if ‘N’ is odd, then ‘N’ - 3 - 2*(‘K’ - 3) is even.
Example: Let ‘N’ be 35 and ‘K’ be 5. Then it can be written as 2, 2, …, ‘K’ - 3 times., i.e., 35 can be written as 2, 2, 3, 5, 23.
Here is the algorithm :
- Base case
- If ‘N’ is smaller than ‘2*K’.
- If ‘K’ is equal to 1, check if ‘N’ is a prime number or not.
- If ‘K’ is equal to 2.
- If ‘N’ is even, return 1.
- Else, check if ‘N’ - 2, is a prime number or not.
- Finally, return 1.