N ≥ 2K and K ≥ 3: The answer is “Yes”. This is because if N is even, then N − 2(K − 2) is also even, so it is the sum of two primes, say p and q (by Goldbach’s conjecture). Thus, N is the sum of the K primes 2, 2, 2, ..., p, q. And if N is odd, then N − 3 − 2(K − 3) is even, so it is the sum of two primes, say p and q. Thus, N is the sum of the K primes 3, 2, 2, ..., p, q.
That is excellent. Thanks!
]]>Logic please?
Assume that the Goldbach conjecture is true (to the limit in the problem).
Now, break it into cases:
N < 2K: The answer is “No”, because the sum of K primes is at least 2K.
N ≥ 2K and K = 1: The answer is “Yes” if N is prime, and “No” otherwise.
N ≥ 2K, K = 2 and N is even: The answer is “Yes” (by Goldbach’s conjecture).
N ≥ 2K, K = 2 and N is odd: The answer is “Yes” if N − 2 is prime, and “No” otherwise. This is because the sum of two odd primes is even, and the only even prime number is 2, so one of the prime numbers in the sum must be 2.
N ≥ 2K and K ≥ 3: The answer is “Yes”. This is because if N is even, then N − 2(K − 2) is also even, so it is the sum of two primes, say p and q (by Goldbach’s conjecture). Thus, N is the sum of the K primes 2, 2, 2, ..., p, q. And if N is odd, then N − 3 − 2(K − 3) is even, so it is the sum of two primes, say p and q. Thus, N is the sum of the K primes 3, 2, 2, ..., p, q.
Does Goldbach help?
This code uses the Rabin-Miller algorithm and Goldbach conjecture
I believe that this solution works (it is in Python 3)
import math, random, sys
def is_probable_prime(n, k = 7):
if n < 6:
return [False, False, True, True, False, True][n]
elif n & 1 == 0:
return False
else:
s, d = 0, n - 1
while d & 1 == 0:
s, d = s + 1, d >> 1
for a in random.sample(range(2, n - 2), min(n - 4, k)):
x = pow(a, d, n)
if x != 1 and x + 1 != n:
for r in range(1, s):
x = pow(x, 2, n)
if x == 1:
return False
elif x == n - 1:
a = 0
break
if a:
return False
return True
if __name__ == '__main__':
T = int(sys.stdin.readline())
for _ in range(T):
N, K = list(map(int, sys.stdin.readline().split()))
if N < 2 * K:
print('No')
elif K == 1:
print('Yes' if is_probable_prime(N) else 'No')
elif K == 2:
if N % 2 == 0:
print('Yes')
else:
print('Yes' if is_probable_prime(N - 2) else 'No')
else:
print('Yes')