Given a number N. Find if it can be expressed as sum of two prime numbers.
Example 1:
Input: N = 34
Output: "Yes" 
Explanation: 34 can be expressed as 
sum of two prime numbers.
Example 2:
Input: N = 23
Output: "No"
Explanation: 23 cannnot be expressed as
sum of two prime numbers. 
Your Task:  
You dont need to read input or print anything. Complete the function isSumOfTwo() which takes N as input parameter and returns "Yes" if can be expressed as sum of two prime numbers. else return "No".
Expected Time Complexity: O(N*sqrt(N))
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:

    def isSumOfTwo (self, N):

        # code here 

Solutions:
class Solution:

	def isSumOfTwo(self, N):
		if N & 1 == 0:
			return 'Yes'
		N = N - 2
		for i in range(2, N):
			if N % i == 0:
				return 'No'
		else:
			return 'Yes'


class Solution:

	def isSumOfTwo(self, num):

		def isprime(n):
			if n in [2, 3]:
				return True
			if n == 1 or n % 2 == 0 or n % 3 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i += 6
			return True
		if num % 2 == 1:
			return 'Yes' if isprime(num - 2) else 'No'
		for i in range(2, num // 2 + 1):
			if isprime(i) and isprime(num - i):
				return 'Yes'
		return 'No'


class Solution:

	def isSumOfTwo(self, N):

		def isPrime(k):
			ref = int(k ** 0.5) + 1
			if k == 2:
				return True
			elif k & 1:
				for i in range(3, ref, 2):
					if k % i == 0:
						return False
				return True
		if N & 1:
			if isPrime(N - 2):
				return 'Yes'
			return 'No'
		if N == 4:
			return 'Yes'
		for i in range(3, N // 2, 2):
			if isPrime(i) and isPrime(N - i):
				return 'Yes'
		return 'No'


class Solution:

	def sieveOfEratosthenes(self, N):
		prime = [True for i in range(N + 1)]
		p = 2
		while p * p <= N:
			if prime[p]:
				for i in range(p * p, N + 1, p):
					prime[i] = False
			p += 1
		ans = []
		for i in range(2, N + 1):
			if prime[i]:
				ans.append(i)
		return ans

	def isSumOfTwo(self, N):
		ans = self.sieveOfEratosthenes(N)
		i = 0
		j = len(ans) - 1
		while i <= j:
			if ans[i] + ans[j] == N:
				return 'Yes'
			elif ans[i] + ans[j] > N:
				j -= 1
			else:
				i += 1
		return 'No'


class Solution:

	def isSumOfTwo(self, N):

		def check(x):
			for r in range(2, int(x ** 0.5) + 1):
				if x % r == 0:
					return False
			return True
		if N & 1 == 0 or check(N - 2):
			return 'Yes'
		else:
			return 'No'


import math

class Solution:

	def isSumOfTwo(self, N):
		x = [1] * (N + 1)
		x[0] = 0
		x[1] = 0
		z = int(math.sqrt(N))
		for i in range(2, z + 1):
			if x[i]:
				for j in range(i + i, N + 1, i):
					x[j] = 0
		for i in range(len(x)):
			if x[i] == 1:
				if x[N - i] == 1:
					return 'Yes'
		else:
			return 'No'


from math import sqrt

class Solution:

	def isSumOfTwo(self, N):

		def prime(b):
			if b < 2:
				return False
			for i in range(2, int(sqrt(b)) + 1):
				if b % i == 0:
					return False
			return True
		a = [True] * (N + 1)
		l = []
		for i in range(2, int(sqrt(N)) + 1):
			if a[i]:
				for z in range(i + i, N + 1, i):
					a[z] = False
		for p in range(2, len(a)):
			if a[p]:
				l.append(p)
		for j in range(len(l)):
			if prime(N - l[j]):
				return 'Yes'
		return 'No'


class Solution:

	def isSumOfTwo(self, N):
		t = []
		c = 0
		x = (N + 1) * [True]
		x[0] = x[1] = False
		for i in range(2, int(N ** 0.5) + 1):
			for j in range(i + i, N + 1, i):
				x[j] = False
		for i in range(len(x)):
			if x[i] == True:
				r = N - i
				if x[r] == True:
					c = 1
					break
		if c == 0:
			return 'No'
		else:
			return 'Yes'


import math

class Solution:

	def isSumOfTwo(self, n):
		l = [True] * (N + 1)
		s = int(math.sqrt(N))
		l[0] = False
		l[1] = False
		for i in range(2, s + 1):
			if l[i]:
				for j in range(i + i, N + 1, i):
					l[j] = False
		k = []
		for i in range(len(l)):
			if l[i]:
				k.append(i)
		i = 0
		j = len(k) - 1
		c = 0
		while i <= j:
			if k[i] + k[j] > N:
				j -= 1
			elif k[i] + k[j] < N:
				i += 1
			elif k[i] + k[j] == N:
				i += 1
				j -= 1
				c += 1
				break
		if c != 0:
			return 'Yes'
		else:
			return 'No'


import math

class Solution:

	def isSumOfTwo(self, N):
		s = [True] * (N + 1)
		s[0] = False
		s[1] = False
		a = int(math.sqrt(N + 1))
		for i in range(2, a + 1):
			if s[i]:
				for j in range(i + i, N + 1, i):
					s[j] = False
		for i in range(len(s)):
			if s[i] == True:
				if s[N - i] == True:
					return 'Yes'
		else:
			return 'No'


import math

class Solution:

	def isSumOfTwo(self, N):
		s = int(math.sqrt(N) + 1)
		v = (N + 1) * [1]
		d = []
		for i in range(s + 1):
			if i < 2:
				v[i] = 0
			if v[i]:
				for j in range(i + i, N + 1, i):
					v[j] = 0
		for i in range(len(v)):
			if v[i] == 1:
				if v[N - i] == 1:
					return 'Yes'
		else:
			return 'No'


import math

def sieve(N):
	a = [1] * (N + 1)
	a[0] = 0
	a[1] = 0
	b = []
	s = int(math.sqrt(N))
	for i in range(2, s + 1):
		if a[i]:
			for j in range(2 * i, N + 1, i):
				a[j] = 0
	for i in range(N + 1):
		if a[i] == 1:
			b.append(i)
	return b

class Solution:

	def isSumOfTwo(self, N):
		a = 3
		b = N - 3
		c = sieve(N)
		if N - 2 in c:
			return 'Yes'
		while a < b:
			for i in range(N // 2):
				if a + b == N and a in c and (b in c):
					return 'Yes'
				else:
					a += 2
					if b % 2 == 1:
						b -= 2
					else:
						b -= 1
		return 'No'


import math as m

class Solution:

	def isSumOfTwo(self, n):
		if n == 4:
			return 'Yes'
		s = [True] * (n + 1)
		s[0] = s[1] = False
		for i in range(2, m.ceil(m.sqrt(n)) + 1):
			if s[i]:
				for j in range(i + i, len(s), i):
					s[j] = False
		a = [i for i in range(len(s)) if s[i]]
		(i, j) = (0, len(a) - 1)
		while i < j:
			if a[i] + a[j] == n:
				return 'Yes'
			elif a[i] + a[j] > n:
				j -= 1
			else:
				i += 1
		return 'No'


import math

def isprime(c):
	if c < 2:
		return False
	for i in range(2, int(math.sqrt(c)) + 1):
		if c % i == 0:
			return False
	return True

class Solution:

	def isSumOfTwo(self, N):
		if 1 + N - 1 == N and isprime(N - 1) == True:
			return 'Yes'
		if 2 + N - 2 == N and isprime(N - 2) == True:
			return 'Yes'
		a = 3
		b = N - 3
		while a < b:
			if a + b == N and isprime(a) == True and (isprime(b) == True):
				return 'Yes'
			else:
				a += 2
				if b % 2 == 0:
					b -= 1
				else:
					b -= 2
		return 'No'


import math

class Solution:

	def isSumOfTwo(self, n):
		if n % 2 == 0:
			return 'Yes'
		else:
			w = n - 2
			for i in range(2, n // 2):
				if w % i == 0:
					return 'No'
			return 'Yes'


import math

class Solution:

	def isprime(self, n):
		if n <= 1 or (n > 2 and n % 2 == 0):
			return False
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				return False
		return True

	def isSumOfTwo(self, N):
		for i in range(2, N // 2 + 1):
			if self.isprime(i) and self.isprime(N - i):
				return 'Yes'
		return 'No'


import math
import math

class Solution:

	def isSumOfTwo(self, N):
		if N % 2 == 0:
			return 'Yes'
		elif is_prime(N - 2):
			return 'Yes'
		else:
			return 'No'

def is_prime(num):
	if num == 1:
		return False
	sq = int(math.sqrt(num))
	for i in range(2, sq + 1):
		if num % i == 0:
			return False
	return True


class Solution:

	def isSumOfTwo(self, N):
		x = (N + 1) * [1]
		x[0] = x[1] = 0
		for i in range(2, int(N ** 0.5) + 1):
			if x[i]:
				for j in range(i * i, N + 1, i):
					x[j] = 0
		primes = [i for i in range(len(x)) if x[i]]
		low = 0
		high = len(primes) - 1
		pos = False
		while low <= high:
			res = primes[low] + primes[high]
			if res == N:
				pos = True
				break
			elif res > N:
				high -= 1
			else:
				low += 1
		return 'Yes' if pos else 'No'


class Solution:

	def is_prime(n):
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return 0
		return 1

	def isSumOfTwo(self, N):
		if N == 2:
			return 'No'
		elif N % 2 == 0:
			return 'Yes'
		elif Solution.is_prime(N - 2):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isSumOfTwo(self, N):
		is_prime = [True] * (N + 1)
		for i in range(2, int(N ** 0.5) + 1):
			if is_prime[i]:
				for j in range(i * i, N + 1, i):
					is_prime[j] = False
		for i in range(2, N // 2 + 1):
			if is_prime[i] and is_prime[N - i]:
				return 'Yes'
		return 'No'


class Solution:

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

	def ispossible(self, N):
		if N < 4:
			return False
		if N % 2 == 0:
			return True
		return self.isprime(N - 2)

	def isSumOfTwo(self, N):
		if self.ispossible(N):
			return 'Yes'
		else:
			return 'No'


import math

class Solution:

	def is_prime(self, n):
		if n <= 1:
			return False
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				return False
		return True

	def isSumOfTwo(self, n):
		if n % 2:
			if self.is_prime(n - 2):
				return 'Yes'
			else:
				return 'No'
		if n == 4:
			return 'Yes'
		for i in range(3, n // 2, 2):
			if self.is_prime(i):
				if self.is_prime(n - i):
					return 'Yes'
		return 'NO'


class Solution:

	def isprime(self, n):
		for j in range(2, n):
			if n % j == 0:
				return False
		return True

	def isSumOfTwo(self, N):
		if N == 4:
			return 'Yes'
		if N % 2 == 1:
			if self.isprime(N - 2):
				return 'Yes'
			else:
				return 'No'
		else:
			for i in range(1, N + 1):
				if self.isprime(i) and self.isprime(N - i):
					return 'Yes'
			return 'No'


import math

class Solution:

	def isPrime(self, N):
		if N == 1:
			return False
		if N == 2 or N == 3:
			return True
		for i in range(2, int(math.sqrt(N)) + 1):
			if N % i == 0:
				return False
		return True

	def isSumOfTwo(self, N):
		if N < 3:
			return 'No'
		elif N % 2 == 0:
			return 'Yes'
		if self.isPrime(N - 2):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isSumOfTwo(self, n):
		a = [1] * (n + 1)
		a[0] = 0
		a[1] = 0
		for i in range(2, n + 1):
			if a[i]:
				for j in range(i * i, n + 1, i):
					a[j] = 0
		c = n // 2
		i = 2
		while i <= c:
			if a[i]:
				s = n - i
				if a[s]:
					return 'Yes'
			i += 1
		return 'No'


import math

class Solution:

	def primes(self, n):
		pl = [True] * (n + 1)
		pl[0] = pl[1] = False
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			if pl[i]:
				for j in range(i * i, n + 1, i):
					pl[j] = False
		res = []
		for i in range(2, n + 1):
			if pl[i]:
				res.append(i)
		return res

	def isSumOfTwo(self, N):
		if N == 1 or N == 2 or N == 3:
			return 'No'
		else:
			sl = self.primes(N)
			(p1, p2) = (0, len(sl) - 1)
			while p1 <= p2:
				if sl[p1] + sl[p2] == N:
					return 'Yes'
				elif sl[p1] + sl[p2] > N:
					p2 -= 1
				else:
					p1 += 1
			return 'No'


class Solution:

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

	def isSumOfTwo(self, N):
		if N & 1 == 0:
			return 'Yes'
		N = N - 2
		for i in range(2, N):
			if N % i == 0:
				return 'No'
		else:
			return 'Yes'


from math import sqrt

class Solution:

	def check(self, n):
		flag = 1
		if n > 1:
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					flag = 0
					break
			if flag == 0:
				return 0
			else:
				return 1
		return 0

	def isSumOfTwo(self, N):
		if N % 2 == 0:
			return 'Yes'
		else:
			a = N - 2
			if self.check(a):
				return 'Yes'
			return 'No'


import math

class Solution:

	def isPrime(N):
		if N < 2:
			return False
		elif N == 2:
			return True
		else:
			for j in range(2, int(math.sqrt(N)) + 1):
				if N % j == 0:
					return False
			return True

	def isSumOfTwo(self, N):
		i = 0
		j = 0
		k = 0
		l = 0
		for i in range(2, N):
			if i > N - i:
				break
			if (i == 2 or N - i == 2) or (i % 2 != 0 and (N - i) % 2 != 0):
				if Solution.isPrime(i) and Solution.isPrime(N - i):
					return 'Yes'
		return 'No'
		return 'No'


class Solution:

	def isPrime(self, x):
		i = 2
		while i * i <= x:
			if x % i == 0:
				return False
			i += 1
		return True

	def isPossible(self, N):
		if N < 4:
			return False
		if N % 2 == 0:
			return True
		return self.isPrime(N - 2)

	def isSumOfTwo(self, N):
		if self.isPossible(N):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isPrime(self, number):
		if number < 1:
			return False
		else:
			for i in range(2, int(number ** 0.5) + 1):
				if number % i == 0:
					return False
		return True

	def findPrimes(self, N):
		if N % 2 == 0:
			return 'Yes'
		elif self.isPrime(N - 2):
			return 'Yes'
		return 'No'

	def isSumOfTwo(self, N):
		return self.findPrimes(N)


class Solution:

	def isSumOfTwo(self, N):
		for i in range(2, N // 2 + 1):
			a = i
			b = N - i
			a_prime = True
			b_prime = True
			x = max(a, b)
			for j in range(2, int(x ** 0.5) + 1):
				if a % j == 0 and a != 2:
					a_prime = False
					break
				if b % j == 0:
					b_prime = False
					break
			else:
				return 'Yes'
		return 'No'


import math

class Solution:

	def isSumOfTwo(self, N):

		def isPrime(N):
			if N == 1:
				return 0
			for i in range(2, int(math.sqrt(N)) + 1):
				if N % i == 0:
					return 0
			return 1
		if N % 2 == 0:
			return 'Yes'
		else:
			if N > 4:
				if isPrime(N - 2) == 1:
					return 'Yes'
				return 'No'
			if N == 1:
				return 'No'
			if N == 3:
				return 'No'
			if N == 2:
				return 'No'
			if N == 4:
				return 'Yes'


import math

class Solution:

	def isSumOfTwo(self, N):

		def checkPrime(n):
			if n == 1:
				return False
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		d = {}
		if N == 0 or N == 1:
			return 'No'
		if N % 2 == 0 or checkPrime(N - 2):
			return 'Yes'
		return 'No'


import math

class Solution:

	def isPrime(self, n):
		i = 2
		l = int(math.sqrt(n)) + 1
		while i < l:
			if n % i == 0:
				return False
			i += 1
		return True

	def isSumOfTwo(self, N):
		if N % 2 != 0:
			if Solution.isPrime(self, N - 2):
				return 'Yes'
			else:
				return 'No'
		li = [0] * (N + 1)
		for i in range(2, N // 2 + 1):
			if Solution.isPrime(self, i):
				li[i] = 1
				if li[N - i] == 1:
					return 'Yes'
				elif Solution.isPrime(self, N - i):
					return 'Yes'
		return 'No'


class Solution:

	def isSumOfTwo(self, N):
		if N % 2 == 0 and N > 2:
			return 'Yes'
		elif N > 1 and self.isPrime(N - 2):
			return 'Yes'
		else:
			return 'No'

	def isPrime(self, N):
		i = 2
		x = N ** (1 / 2)
		while N == 1 or i <= x:
			if N == 1 or N % i == 0:
				return False
			i += 1
		return True


class Solution:

	def isSumOfTwo(self, N):

		def check(i):
			for j in range(2, i // 2 + 1):
				if i % j == 0:
					break
			else:
				return True
		if N < 4:
			return 'No'
		elif N % 2 == 0:
			return 'Yes'
		if check(N - 2):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isSumOfTwo(self, n):

		def prime(n):
			if n == 2:
				return True
			if n < 2:
				return False
			for i in range(3, int(n ** 0.5) + 1, 2):
				if not n % i:
					return False
			return True
		if n < 4:
			return 'No'
		if n % 2:
			if prime(n - 2):
				return 'Yes'
			else:
				return 'No'
		if n == 4:
			return 'Yes'
		for i in range(2, n):
			if prime(i) and prime(n - i):
				return 'Yes'
				break
		else:
			return 'No'


class Solution:

	def isSumOfTwo(self, N):
		candidates = sieve(N)
		if N % 2 != 0:
			if N - 2 in candidates:
				return 'Yes'
			else:
				return 'No'
		else:
			for i in range(2, N // 2 + 1):
				if i in candidates and N - i in candidates:
					return 'Yes'
			return 'No'

def sieve(n):
	possible = [True] * (n + 1)
	p = 2
	while p * p < n:
		if possible[p]:
			for j in range(p * p, n + 1, p):
				possible[j] = False
		p += 1
	res = []
	for i in range(n + 1):
		if possible[i]:
			res.append(i)
	return res


import math

def isprime(N):
	l = int(math.sqrt(N))
	for i in range(2, l + 2):
		if N % i == 0:
			return False
	return True

class Solution:

	def isSumOfTwo(self, N):
		if N == 2 or N == 3:
			return 'Yes'
		m = int(math.sqrt(N) + 1)
		if N % 2 == 1:
			c = 1
			for i in range(2, m + 1):
				if (N - 2) % i == 0:
					c = 0
					i = m
			if c == 1:
				return 'Yes'
			else:
				return 'No'
		for i in range(N + 1):
			if isprime(i) and isprime(N - i):
				return 'Yes'
		return 'No'


class Solution:

	def isPrime(self, N):
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				return 'No'
		return 'Yes'

	def isSumOfTwo(self, N):
		if N < 3:
			return 'No'
		elif N % 2 == 0:
			return 'Yes'
		return self.isPrime(N - 2)


class Solution:

	def isSumOfTwo(self, n):
		primes = [True for i in range(n + 1)]
		p = 2
		while p * p <= n:
			if primes[p]:
				for i in range(p * p, n + 1, p):
					primes[i] = False
			p += 1
		for i in range(2, n):
			if primes[i] and primes[n - i]:
				return 'Yes'
		return 'No'


class Solution:

	def isSumOfTwo(self, N):

		def isPrime(n):
			k = int(n ** 0.5) + 1
			for i in range(3, k, 2):
				if n % i == 0:
					return False
			return True
		if N < 4:
			return 'No'
		if not N % 2:
			return 'Yes'
		if isPrime(N - 2):
			return 'Yes'
		return 'No'


def isPrime(n, r=False):
	if n < 4:
		return n > 1
	(isDivisible, k, i) = (lambda n, i, r: n if n % i else i if r else r, int(n ** 0.5), 2)
	while i <= k:
		d = isDivisible(n, i, r)
		if d - n:
			return d
		i += i - 1 if i in (2, 3) else (i - 3) % 6
	return True

class Solution:

	def isSumOfTwo(self, N):
		if N % 2:
			if isPrime(N - 2):
				return 'Yes'
			return 'No'
		if N <= 2:
			return 'No'
		return 'Yes'


class Solution:

	def prime(self, n):
		if n % 2 == 0:
			return 0
		elif n == 2 or n == 1:
			return 1
		else:
			for i in range(3, int(n ** 0.5) + 1, 2):
				if n % i == 0:
					return 0
			else:
				return 1

	def isSumOfTwo(self, n):
		k = 0
		for i in range(2, n):
			if self.prime(i) and self.prime(n - i):
				k = 1
				break
		if k == 1:
			return 'Yes'
		else:
			return 'No'

class Solution:

	def isPrime(self, x):
		i = 2
		while i * i <= x:
			if x % i == 0:
				return False
			i += 1
		return True

	def isPossible(self, N):
		if N < 4:
			return False
		if N % 2 == 0:
			return True
		return self.isPrime(N - 2)

	def isSumOfTwo(self, N):
		if self.isPossible(N):
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isSumOfTwo(self, N):
		p = [0] * (N + 1)
		p[0] = p[1] = False
		for i in range(2, N + 1):
			p[i] = True
		k = 2
		while k * k < N:
			if p[k] == True:
				i = k * k
				while i <= N:
					p[i] = False
					i += k
			k += 1
		for i in range(N):
			if p[i] and p[N - i]:
				return 'Yes'
		return 'No'


class Solution:

	def isSumOfTwo(self, N):
		loop = N // 2
		for i in range(2, loop + 1):
			if self.is_prime(i) and self.is_prime(N - i):
				return 'Yes'
		else:
			return 'No'

	def is_prime(self, num):
		if num % 2 == 0 and num != 2:
			return False
		for i in range(3, int(num ** 0.5) + 1, 2):
			if num % i == 0:
				return False
		else:
			return True


class Solution:

	def isSumOfTwo(self, N: int) -> str:
		if N < 4:
			return 'No'
		prime_numbers = self.seiveEratosthenes(N)
		seen = set()
		for prime_number in prime_numbers:
			target = N - prime_number
			if 2 * prime_number == N:
				return 'Yes'
			elif target in seen:
				return 'Yes'
			else:
				seen.add(prime_number)
		return 'No'

	@staticmethod
	def seiveEratosthenes(n: int) -> list:
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(2, int(n ** 0.5) + 1):
			if primes[i]:
				for x in range(i ** 2, n, i):
					primes[x] = False
		return [z for z in range(n) if primes[z]]


class Solution:

	def isSumOfTwo(self, N):

		def seive(N):
			x = [True for i in range(N + 1)]
			x[0] = x[1] = False
			i = 2
			while i * i <= N:
				if x[i]:
					for j in range(i * i, N + 1, i):
						x[j] = False
				i += 1
			return x
		isp = seive(N)
		for i in range(N):
			if isp[i] and isp[N - i]:
				return 'Yes'
		return 'No'