Given a number N, the task is to express N as a summation of 4 positive primes.
 
Example 1:
Input: N = 8
Output: 2 2 2 2
Explanation: 2 is prime and 2 + 2 + 2 + 2 = 8
Example 2:
Input: N = 15
Output: 2 3 3 7
Explanation: 2, 3 and 7 are prime and 2 + 3 + 
+ 3 + 7 = 15.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Express() which takes N as input parameter and returns a list of four number if N can be expressed as a summation of four numbers otherwise returns a list containing -1. The returned list should be in increasing order. If there are more than one list possible then returns the lexicograhically smallest one.
 
Expected Time Complexity: O(N*log(N))
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:
	def Express(self, N):
		# Code here

Solutions:
class Solution:

	def Express(self, N):
		if N < 8:
			return [-1]
		if N % 2 == 0:
			result = [2, 2]
			result.extend(self.otherTwo(N - 4))
			return sorted(result)
		else:
			result = [2, 3]
			result.extend(self.otherTwo(N - 5))
			return sorted(result)

	def otherTwo(self, N):
		for i in range(2, N // 2 + 1, 1):
			if self.isPrime(i) and self.isPrime(N - i):
				return [i, N - i]
		return [-1]

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


import math

class Solution:

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

	def Num(self, x):
		ab = [0] * 2
		for i in range(2, int(x / 2) + 1):
			if self.isPrime(i) != 0 and self.isPrime(x - i) != 0:
				ab[0] = i
				ab[1] = x - i
				return ab

	def Express(self, N):
		if N <= 7:
			return [-1]
		if N % 2 != 0:
			ab = self.Num(N - 5)
			return sorted([2, 3, ab[0], ab[1]])
		else:
			bb = self.Num(N - 4)
			return [2, 2, bb[0], bb[1]]