Given two numbers N and K. Find out if ‘N’ can be written as a sum of ‘K’ prime numbers.
Input:
N = 10 and K = 2
Output: 1
Explanation:
10 can be written as 5 + 5
 
Example 2:
Input:
N = 2 and K = 2
Output: 0
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isSumOfKprimes() which takes the integer N and an integer K as input parameters and returns the true if N can be expressed as a sum of K primes else return false.
If function returns true, driver code will print 1 in output and 0 if the function returns false.
Expected Time Complexity: O(SQRT(N))
Expected Auxiliary Space: O(1)
 
 
Constraints:
1 <= N,K <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3



class Solution:

    def isSumOfKprimes (self, N, K):

        pass

        # code here

        



Solutions:
class Solution:

	def isSumOfKprimes(self, N, k):

		def isprime(n):
			if n == 1:
				return False
			i = 2
			while i * i <= n:
				if n % i == 0:
					return False
				i += 1
			return True
		if k == 1:
			return isprime(N)
		if N % 2 == 0 and k == 2:
			return True
		if N % 2 == 1 and k == 2:
			return isprime(N - 2)
		if k >= 3:
			return N >= 2 * k


class Solution:

	def isSumOfKprimes(self, n, k):

		def isprime(x):
			i = 2
			while i * i <= x:
				if x % i == 0:
					return 0
				i += 1
			return 1
		if n < 2 * k:
			return 0
		if k == 1:
			return isprime(n)
		if k == 2:
			if n % 2 == 0:
				return 1
			return isprime(n - 2)
		return 1


from math import sqrt

class Solution:

	def isSumOfKprimes(self, n, k):

		def isprime(n):
			if n < 2:
				return False
			if n == 2 or n == 3:
				return True
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		if n >= 2 * k and k == 1:
			if isprime(n):
				return True
			else:
				return False
		if n >= 2 * k and k == 2:
			if n % 2 == 0:
				return True
			elif isprime(n - 2):
				return True
			else:
				return False
		if n >= 2 * k and k >= 3:
			return True


class Solution:

	def isprime(self, n):
		for i in range(2, int(pow(n, 0.5)) + 1):
			if n % i == 0:
				return False
		return True

	def isSumOfKprimes(self, n, k):
		if k > n // 2:
			return False
		if k == 1:
			if self.isprime(n):
				return True
			return False
		if k == 2:
			if n % 2 == 0:
				return True
			else:
				return self.isprime(n - 2)
		return True


from math import sqrt

def prime(n):
	if n <= 1:
		return 0
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return 0
	else:
		return 1

class Solution:

	def isSumOfKprimes(self, N, K):
		if N < 2 * K:
			return 0
		if K == 1:
			return prime(N)
		if K == 2:
			if N % 2 == 0:
				return 1
			return prime(N - 2)
		if K >= 3:
			return 1


def isprime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return 0
		i += 1
	return 1

class Solution:

	def isSumOfKprimes(self, N, K):
		if N < 2 * K:
			return 0
		if K == 1:
			return isprime(N)
		if K == 2:
			if N % 2 == 0:
				return 1
			return isprime(N - 2)
		return 1