Given a number N,  find if N can be expressed as a + b  such that a and b are prime.
Note: If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, and a < c then  [a, b] is considered as our answer.
 
Example 1:
Input:
N = 8
Output:
3 5
Explanation:
3 and 5 are both prime and they
add up to 8.
Example 2:
Input:
N = 3
Output:
-1 -1
Explanation:
There are no solutions to the number 3.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getPrimes() which takes an integer n as input and returns (a,b) as an array of size 2. 
Note: If no value of (a,b) satisfy the condition return (-1,-1) as an array of size 2.
 
Expected Time Complexity: O(N*loglog(N))
Expected Auxiliary Space: O(N)
 
Constraints:
2 <= N <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Starter code: #User function Template for python3



class Solution:

    def getPrimes(self, N):

        # code here

Solutions:
import math

class Solution:

	def getPrimes(self, N):
		result = []

		def checkPrime(n):
			for i in range(2, n // 2):
				if n % i == 0:
					return False
			return True
		if checkPrime(N - 2) and N - 2 > 0:
			return [2, N - 2]
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			if checkPrime(i) and checkPrime(N - i):
				return [i, N - i]
		return [-1, -1]


class Solution:

	def getPrimes(self, N):
		arr = [1] * (N + 1)
		for i in range(2, N + 1):
			if arr[i] == 1:
				for j in range(i * i, N + 1, i):
					arr[j] = 0
		f = 1
		arr[0] = arr[1] = 0
		for i in range(2, N + 1):
			if arr[i] == 1 and arr[N - i] == 1:
				return [i, N - i]
		return [-1, -1]


class Solution:

	def getPrimes(self, N):
		if N <= 3:
			return [-1, -1]
		sieve = [True] * N
		if N == 0 or N == 1:
			return 0
		(sieve[0], sieve[1]) = (False, False)
		for i in range(2, int(N ** 0.5) + 1):
			if sieve[i]:
				for j in range(i + i, N, i):
					sieve[j] = False
		for i in range(N // 2 + 1):
			if sieve[i] and sieve[N - i]:
				return [i, N - i]
		return [-1, -1]


from math import *

class Solution:

	def getPrimes(self, N):

		def sieve(n):
			prime = [True] * (n + 1)
			p = 2
			while p * p <= n:
				if prime[p] == True:
					for i in range(p * p, n + 1, p):
						prime[i] = False
				p += 1
			return prime
		if N == 1 or N == 2:
			return [-1, -1]
		else:
			l = sieve(N)
			for i in range(2, N):
				if l[i] == 1 and l[N - i] == 1:
					return [i, N - i]
			return [-1, -1]


class Solution:

	def findPrime(self, N):
		self.prime = [True if i > 1 else False for i in range(N + 1)]
		for i in range(2, N + 1):
			if not self.prime[i]:
				continue
			for j in range(2 * i, N + 1, i):
				self.prime[j] = False

	def getPrimes(self, N):
		if N < 4:
			return (-1, -1)
		self.prime = None
		self.findPrime(N)
		(res1, res2) = (-1, -1)
		for i in range(2, N):
			if self.prime[i] and self.prime[N - i]:
				return (i, N - i)
		return (-1, -1)


class Solution:

	def getPrimes(self, N):
		l = []
		prime = [True for _ 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
		for i in range(2, N):
			if prime[i] and prime[N - i]:
				return [i, N - i]
		return [-1, -1]


class Solution:

	def sieve_of_Sundaram(self, n):
		k = (n - 1) // 2
		integers_list = [True] * (k + 1)
		for i in range(1, k + 1):
			j = i
			while i + j + 2 * i * j <= k:
				integers_list[i + j + 2 * i * j] = False
				j += 1
		for i in range(1, k + 1):
			if integers_list[i]:
				yield (2 * i + 1)

	def getPrimes(self, N):
		listPrimes = list(self.sieve_of_Sundaram(N))
		countPrimes = len(listPrimes)
		if N == 4:
			return [2, 2]
		if N % 2 == 0:
			for p in listPrimes:
				if (N - p) % 2 == 0 or (N - p) % 3 == 0:
					continue
				if N - p in listPrimes:
					return [p, N - p]
		elif N - 2 in listPrimes:
			return [2, N - 2]
		return [-1, -1]


class Solution:

	def getPrimes(self, N):
		from math import sqrt

		def prime(N):
			for i in range(2, int(sqrt(N)) + 1):
				if N % i == 0:
					return 0
			return 1
		k = []
		for i in range(2, N // 2 + 1):
			if prime(i) and prime(N - i):
				k.append(i)
				k.append(N - i)
				return k
		k.append(-1)
		k.append(-1)
		return k


class Solution:

	def getPrimes(self, N):
		from math import sqrt

		def fun(n):
			c = 0
			if n <= 1:
				return 0
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					return 0
			return 1
		k = []
		for i in range(2, N // 2 + 1):
			if fun(i) == 1 and fun(N - i) == 1:
				k.append(i)
				k.append(N - i)
				return k
		else:
			k.append(-1)
			k.append(-1)
			return k


class Solution:

	def getPrimes(self, n):
		import math

		def is_prime(k):
			a = int(math.sqrt(k))
			if k <= 1:
				return 0
			for i in range(2, a + 1):
				if k % i == 0:
					return 0
			else:
				return 1
		l = []
		for i in range(1, n // 2 + 1):
			if is_prime(i) and is_prime(n - i):
				l.append(i)
				l.append(n - i)
				return l
		else:
			l.append(-1)
			l.append(-1)
			return l


import math

class Solution:

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

	def getPrimes(self, N):
		c = 0
		if N % 2 != 0:
			if self.Isprime(N - 2):
				c = 1
				return [2, N - 2]
		else:
			for i in range(3, N):
				if self.Isprime(i):
					if self.Isprime(N - i):
						c = 1
						return [i, N - i]
		if c == 0:
			return [-1, -1]


import math

class Solution:

	def getPrimes(self, n):

		def isprime(n):
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		for i in range(2, n // 2):
			if isprime(i) and isprime(n - i):
				return [i, n - i]
		return [-1, -1]


class Solution:

	def Sieve(self, num, l):
		prime = [True for i in range(num + 1)]
		p = 2
		while p * p <= num:
			if prime[p] == True:
				for i in range(p * p, num + 1, p):
					prime[i] = False
			p += 1
		for p in range(2, num + 1):
			if prime[p]:
				l.append(p)
				l.append(p)

	def getPrimes(self, N):
		l = []
		self.Sieve(N, l)
		i = 0
		j = len(l) - 1
		while i < j:
			if l[i] + l[j] == N:
				return [l[i], l[j]]
			if l[i] + l[j] < N:
				i += 1
			else:
				j -= 1
		return [-1, -1]


from math import sqrt

class Solution:

	def getPrimes(self, N):
		ans = []
		for i in range(1, N // 2 + 1):
			if self.findprimes(i) and self.findprimes(N - i):
				ans.append(i)
				ans.append(N - i)
				return ans
		ans.extend([-1, -1])
		return ans

	def findprimes(self, N):
		if N <= 1:
			return 0
		for i in range(2, int(sqrt(N)) + 1):
			if N % i == 0:
				return 0
		return 1


import math

class Solution:

	def generatePrimes(n):
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(4, n, 2):
			primes[i] = False
		for i in range(3, int(math.sqrt(n))):
			if primes[i]:
				for j in range(i * i, n, i):
					primes[j] = False
		return primes
	n = 10000000
	primes = generatePrimes(n)

	def getPrimes(self, N):
		length = len(self.primes)
		for i in range(length):
			diff = N - i
			if self.primes[i] and self.primes[diff]:
				return [i, diff]
			if diff < 0:
				return [-1, -1]
		return [-1, -1]


class Solution:

	def getPrimes(self, N):

		def isPrime(num):
			if num < 2:
				return 0
			for i in range(2, int(num ** 0.5) + 1):
				if num % i == 0:
					return 0
			return 1
		prime = [True] * (N + 1)
		for i in range(2, int(N ** 0.5) + 1):
			if prime[i] == True:
				for j in range(i * i, N + 1, i):
					prime[j] = False
		ans = [-1] * 2
		for i in range(2, len(prime)):
			if prime[i] == True:
				if isPrime(N - i) == True:
					ans[0] = i
					ans[1] = N - i
					break
		return ans


class Solution:

	def getPrimes(self, N):

		def p(n):
			if n <= 2:
				return []
			is_prime = [True] * n
			is_prime[0] = False
			is_prime[1] = False
			for i in range(2, int(n ** 0.5) + 1):
				if is_prime[i]:
					for x in range(i * i, n, i):
						is_prime[x] = False
			return [i for i in range(n) if is_prime[i]]
		a = p(N + 1)
		d = {}
		for i in a:
			d[i] = 1
		ans = []
		for i in a:
			t = N - i
			if t in d:
				ans.append(i)
				ans.append(t)
				break
		if ans:
			return ans
		return [-1, -1]


class Solution:

	def getPrimes(self, N):
		prime = [True] * (N + 1)
		prime[0] = False
		prime[1] = False
		for p in range(2, int(N ** 0.5) + 1):
			if prime[p] == True:
				for i in range(p * p, N + 1, p):
					prime[i] = False
		ans = []
		for i in range(0, N + 1):
			if prime[i] == True and prime[N - i] == True:
				ans.append([i, N - i])
		if ans:
			return ans[0]
		return [-1, -1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.getPrimes(N)
		print(ptr[0], ptr[1])


class Solution:

	def isPrime(n):
		d = 2
		while d * d <= n:
			if n % d == 0:
				return 0
			d += 1
		return 1

	def getPrimes(self, n):
		i = 2
		j = n - 1
		while i <= j:
			sm = i + j
			if sm > n:
				j -= 1
			elif sm < n:
				i += 1
			elif Solution.isPrime(i) == 1 and Solution.isPrime(j) == 1:
				return [i, j]
			else:
				i += 1
				j -= 1
		return [-1, -1]


class Solution:

	def is_prime(self, num):
		if num <= 1:
			return False
		for j in range(2, int(num ** (1 / 2)) + 1):
			if num % j == 0:
				return False
		return True

	def getPrimes(self, n):
		if n % 2 != 0:
			if self.is_prime(n - 2) == True:
				return [2, n - 2]
			else:
				return [-1, -1]
		elif n == 4:
			return [2, 2]
		else:
			for i in range(3, n // 2):
				if self.is_prime(i) == True:
					if self.is_prime(n - i) == True:
						return [i, n - i]
			return [-1, -1]


class Solution:

	def getPrimes(self, N):
		if N <= 3:
			return [-1, -1]
		isprime = [True for i in range(N)]
		isprime[0] = isprime[1] = False
		for i in range(2, N):
			if isprime[i] == True:
				j = 2 * i
				while j < N:
					isprime[j] = False
					j += i
		for i in range(2, N // 2 + 1):
			if isprime[i] == True and isprime[N - i] == True:
				return [i, N - i]
		return [-1, -1]


mod = int(1000000.0 + 1)

def seive(n, dp):
	n = n + 1
	for i in range(3, n, 2):
		dp[i] = 1
	for i in range(3, n, 2):
		for j in range(i * i, n, i):
			if dp[j] == 1:
				dp[j] = 0
	dp[0] = dp[1] = 0
	dp[2] = 1

class Solution:

	def getPrimes(self, N):
		dp = [0 for i in range(N + 1)]
		seive(N, dp)
		if dp[N] == 1:
			return [-1, -1]
		for i in range(2, N):
			if dp[i] == 1 and dp[N - i] == 1:
				return [i, N - i]
		return [-1, -1]