#C5063. Sum of T Primes
Sum of T Primes
Sum of T Primes
You are given two positive integers \(K\) and \(T\). The task is to determine whether it is possible to represent \(K\) as the sum of exactly \(T\) prime numbers.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, ... are prime numbers.
The problem can be broken down as follows:
- If \(T = 1\), then you only need to check whether \(K\) is a prime number.
- If \(T = 2\), then provided \(K \ge 4\) (since the smallest sum of two primes is \(2+2=4\)), you should output "Yes". (Note that according to the problem constraints, and based on provided test cases, if \(T = 2\) and \(K \ge 4\), the answer is always "Yes".)
- If \(T \ge 3\), a recursive approach can be used: iterate through possible prime numbers \(p\) and check if \(K-p\) can be decomposed into a sum of \(T-1\) primes.
Note: In this problem, if \(T \times 2 > K\) then it is impossible to represent \(K\) as a sum of \(T\) primes, and the answer should be "No".
The input will be taken from stdin
and the output should be printed to stdout
.
inputFormat
The input consists of a single line containing two integers \(K\) and \(T\) separated by whitespace.
\(1 \leq K, T \leq 10^4\) (the constraints are not strict, but are assumed to allow for a recursive solution).
outputFormat
Output a single line "Yes" if \(K\) can be represented as the sum of exactly \(T\) prime numbers, otherwise output "No".
## sample10 2
Yes