Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer n. Find a set of numbers p_{i} (1 ≤ i ≤ k), such that



 1 ≤ k ≤ 3

 p_{i} is a prime

 $\sum_{i = 1}^{k} p_{i} = n$

The numbers p_{i} do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.


-----Input-----

The single line contains an odd number n (3 ≤ n < 10^9).


-----Output-----

In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.

In the second line print numbers p_{i} in any order. If there are multiple possible solutions, you can print any of them.


-----Examples-----
Input
27

Output
3
5 11 11



-----Note-----

A prime is an integer strictly larger than one that is divisible only by one and by itself.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
def main():
	n = int(input())
	limit = int(n ** 0.5) + 1
	lim12 = max(limit, 12)
	lim = lim12 // 6
	l = [False, True, True] * lim
	lim = lim * 3 - 1
	for (i, s) in enumerate(l):
		if s:
			(p, pp) = (i * 2 + 3, (i + 3) * i * 2 + 3)
			le = (lim - pp) // p + 1
			if le > 0:
				l[pp::p] = [False] * le
			else:
				break
	l[3] = True
	primes = [i for (i, s) in zip(list(range(3, lim12, 2)), l) if s]
	for (i, p) in enumerate((3, 5, 7)):
		primes[i] = p
	res = False
	for x in (n, n - 2, n - 4):
		if x > primes[-1]:
			for p in primes:
				if not x % p:
					break
			else:
				res = True
		else:
			res = x in primes
		if res:
			print((n - x) // 2 + 1)
			print(x, *[2] * ((n - x) // 2))
			return
	(l, cache) = ([], set())
	for b in primes:
		l.append(b)
		for c in l:
			a = n - b - c
			if a not in cache:
				for p in primes:
					if not a % p:
						cache.add(a)
						break
				else:
					print(3)
					print(a, b, c)
					return

def __starting_point():
	main()
__starting_point()


import math as ma

def fu(a):
	a -= 4
	while 1 > 0:
		if ise(a):
			return a
			break
		else:
			a -= 1

def ise(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if 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 = i + 6
	return True
n = int(input())
if n == 3 or n == 5:
	print(1)
	print(n)
else:
	print(3)
	b = n
	a = [fu(n)]
	b = b - a[0]
	for i in range(b):
		if ise(i) and ise(b - i):
			a.append(i)
			a.append(b - i)
			break
	print(*a)


n = int(input())
p = lambda x: True if sum((x % i == 0 for i in range(2, int(x ** 0.5) + 1))) == 0 else False
if n == 3 or n == 5:
	print(1)
	print(n)
else:
	for i in range(2, 10 ** 5):
		j = n - i - 3
		if j > 1 and p(i) and p(j):
			print(3)
			print(3, i, j)
			exit()


def isPrime(n):
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, n, 2):
		if i * i > n:
			break
		if n % i == 0:
			return False
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
elif isPrime(n - 2):
	print(2)
	print('2 ' + str(n - 2))
else:
	print(3)
	for i in range(2, n - 3):
		if i > 2 and i % 2 == 0:
			continue
		if n - 3 - i < i:
			break
		if isPrime(i) and isPrime(n - 3 - i):
			print('3 ' + str(i) + ' ' + str(n - 3 - i))
			break


def isPrime(n):
	if n == 3 or n == 2:
		return True
	if 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 = i + 6
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
	exit()
print(3)
n -= 3
for i in range(2, n):
	if isPrime(i) and isPrime(n - i):
		print(3, i, n - i)
		exit()


def is_prime(n):
	if n == 1:
		return False
	for i in range(2, 1 + int(pow(n, 0.5))):
		if n % i == 0:
			return False
	return True
n = int(input())
if is_prime(n):
	print(1)
	print(n)
elif is_prime(n - 2):
	print(2)
	print(2, n - 2)
else:
	n -= 3
	for i in range(3, n // 2 + 1, 2):
		if is_prime(i) and is_prime(n - i):
			print(3)
			print(3, i, n - i)
			break


N = 1000005
siv = [0] * N
siv[0] = 1
siv[1] = 1
prim = []
for i in range(2, N):
	if not siv[i]:
		for j in range(i * i, N, i):
			siv[j] = i
		prim += [i]

def isPrime(n):
	for p in prim:
		if p * p > n:
			break
		if not n % p:
			return False
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
	exit(0)
for i in range(n - 1, 1, -1):
	if isPrime(i):
		q = n - i
		for p in prim:
			r = q - p
			if not siv[r]:
				print(3)
				print(i, p, r)
				exit(0)


from math import sqrt
from array import array
from sys import stdin
input = stdin.readline
n = int(input())
ans = []
if n == 3:
	ans.append(3)
	print('{}'.format(len(ans)) + '\n' + ''.join((str(x) + ' ' for x in ans)))
	exit(0)
N = n
magic_value = 300
primes = array('L')
primes.append(2)
lim = int(sqrt(N)) + 1
for number in range(3, lim, 2):
	isPrime = True
	for prime in primes:
		if number % prime == 0:
			isPrime = False
			break
	if isPrime:
		primes.append(number)

def checkPrime(x):
	lim = int(sqrt(x) + 1)
	isPrime = True
	for prime in primes:
		if x % prime == 0:
			isPrime = False
			break
		if prime > lim:
			break
	return isPrime
for sub in range(0, magic_value, 2):
	if checkPrime(n - sub):
		ans.append(n - sub)
		n = sub
		break
if n == 0:
	print('{}'.format(len(ans)) + '\n' + ''.join((str(x) + ' ' for x in ans)))
	exit(0)
for prime in primes:
	if n == prime:
		ans.append(n)
		break
	if n - prime in primes:
		ans.append(prime)
		ans.append(n - prime)
		break
	if prime > n:
		break
print('{}'.format(len(ans)) + '\n' + ''.join((str(x) + ' ' for x in ans)))


import math

def prime(x):
	if x == 1:
		return False
	for i in range(2, math.floor(math.sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True
n = int(input())
if prime(n):
	print(1)
	print(n)
elif prime(n - 2):
	print(2)
	print(n - 2, 2)
elif prime(n - 3):
	print(2)
	print(n - 3, 3)
else:
	x = n - 4
	while not prime(x):
		x -= 1
	rest = n - x
	y = rest - 1
	while not prime(y) or not prime(rest - y):
		y -= 1
	print(3)
	print(x, y, rest - y)


def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def printlist(l):
	print(' '.join([str(x) for x in l]))

def listring(l):
	return ''.join([str(x) for x in l])

def isPrime(n):
	if n == 2 or n == 3:
		return True
	if n < 2:
		return False
	if n % 2 == 0 or n % 3 == 0:
		return False
	if n < 10:
		return True
	p = 5
	while p <= int(n ** 0.5):
		if n % p == 0 or n % (p + 2) == 0:
			return False
		p += 6
	return True
n = it()
if isPrime(n):
	print(1)
	print(n)
elif isPrime(n - 2):
	print(2)
	print('2 %d' % (n - 2))
else:
	r = 4
	while not isPrime(n - r):
		r += 2
	if r == 4:
		(p, q) = (2, 2)
	elif r == 6:
		(p, q) = (3, 3)
	elif r == 8:
		(p, q) = (3, 5)
	elif r == 10:
		(p, q) = (5, 5)
	elif r == 12:
		(p, q) = (5, 7)
	elif isPrime(r - 3):
		(p, q) = (3, r - 3)
	else:
		p = 5
		while not (isPrime(r - p) and isPrime(p)) and (not (isPrime(r - p - 2) and isPrime(p + 2))):
			p += 6
		if isPrime(p) and isPrime(r - p):
			(p, q) = (p, r - p)
		else:
			(p, q) = (p + 2, r - p - 2)
	print(3)
	print('%d %d %d' % (n - r, p, q))


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

def sieve(ub):
	isp = [True] * ub
	isp[0] = isp[1] = False
	p = 2
	while p * p < ub:
		if isp[p]:
			for m in range(p * p, ub, p):
				isp[m] = False
		p += 1
	return isp

def solve(n):
	if is_prime(n):
		return [n]
	if is_prime(n - 2):
		return [2, n - 2]
	p = n - 4
	while not is_prime(p):
		p -= 2
	r = n - p
	isp = sieve(r)
	for k in range(r // 2 + 1):
		if isp[k] and isp[r - k]:
			return [p, k, r - k]
	assert False
n = int(input())
res = solve(n)
print(len(res))
print(*res)


def prime(n):
	if n < 4:
		return n == 2 or n == 3
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
n = int(input())
if prime(n):
	print(1)
	print(n)
elif prime(n - 2):
	print(2)
	print(2, n - 2)
else:
	print(3)
	c = n - 3
	for i in range(3, n, 2):
		if prime(i) and prime(c - i):
			print(3, i, c - i)
			break


def main():
	n = int(input())
	limit = int(n ** 0.5) + 1
	lim12 = max(limit, 12)
	lim = lim12 // 6
	sieve = [False, True, True] * lim
	lim = lim * 3 - 1
	for (i, s) in enumerate(sieve):
		if s:
			(p, pp) = (i * 2 + 3, (i + 3) * i * 2 + 3)
			le = (lim - pp) // p + 1
			if le > 0:
				sieve[pp::p] = [False] * le
			else:
				break
	sieve[3] = True
	primes = [i for (i, s) in zip(list(range(3, lim12, 2)), sieve) if s]
	for (i, p) in enumerate((3, 5, 7)):
		primes[i] = p
	while primes and primes[-1] >= limit:
		del primes[-1]
	for x in (n, n - 2, n - 4):
		for p in primes:
			if not x % p:
				break
		else:
			print((n - x) // 2 + 1)
			print(x, *[2] * ((n - x) // 2))
			return
	for a in range(n // 2 | 1, n, 2):
		for p in primes:
			if not a % p:
				break
		else:
			for c in primes:
				b = n - a - c
				if b < 3:
					break
				for p in primes:
					if not b % p:
						break
				else:
					print(3)
					print(a, b, c)
					return

def __starting_point():
	main()
__starting_point()


def isPrime(n):
	from math import sqrt
	if n == 0 or n == 1:
		return False
	else:
		for check in range(2, int(sqrt(n)) + 1):
			if n % check == 0:
				return False
	return True
n = int(input())
ans = n
for i in range(0, n + 1):
	if isPrime(n - i):
		ans = n - i
		break
rem = n - ans
if rem == 0:
	print(1)
	print(ans)
elif isPrime(rem):
	print(2)
	print('{} {}'.format(ans, rem))
else:
	print(3)
	for i in range(2, rem + 1):
		if isPrime(i) and isPrime(rem - i):
			print('{} {} {}'.format(ans, i, rem - i))
			break


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)

def isPrime(num):
	if num == 1:
		return False
	x = int(math.sqrt(num))
	for i in range(2, x + 1):
		if num % i == 0:
			return False
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
else:
	i = n // 2
	while i > 1:
		if isPrime(i) and isPrime(n - 2 * i):
			print(3)
			print(i, i, n - 2 * i)
			break
		i = i - 1


def prime(n):
	if n in [2, 3]:
		return True
	if n < 2 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

def main():
	(n, ans) = (int(input()), [])
	if prime(n):
		ans = [n]
	else:
		if n & 1:
			n -= 3
			ans.append(3)
		i = 2
		while True:
			if prime(n - i) and prime(i):
				ans.extend([i, n - i])
				break
			i += 1
	print(len(ans))
	print(*ans)
main()


def chek(a):
	for i in range(2, int(a ** 0.5) + 1):
		if a % i == 0:
			return False
	return True
n = int(input())
if n == 3:
	print(1)
	print(3)
	exit()
if n == 5:
	print(1)
	print(5)
	exit()
if n == 7:
	print(1)
	print(7)
	exit()
print(3)
n -= 3
for i in range(2, n):
	if chek(i) and chek(n - i):
		print(3, i, n - i)
		exit()


def isPrime(n):
	i = 2
	while i * i < n + 1:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
if isPrime(n):
	print('1')
	print(n)
elif isPrime(n - 2):
	print('2\n2 ' + str(n - 2))
else:
	temp = n
	while not isPrime(temp) or n - temp < 4:
		temp -= 1
	n -= temp
	for i in range(2, n + 2):
		if isPrime(i) and isPrime(n - i):
			print('3\n' + str(n - i) + ' ' + str(i) + ' ' + str(temp))
			break


import math

def isprime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	for j in range(2, math.ceil(n ** (1 / 2)) + 1):
		if n % j == 0:
			return False
	return True
n = int(input())
t = n
ans = []
while not isprime(n):
	n -= 1
ans.append(n)
rem = t - n
for i in range(2, rem + 1):
	if isprime(i):
		if isprime(rem - i):
			ans.append(i)
			ans.append(rem - i)
			break
		if rem - i == 0:
			ans.append(i)
			break
print(len(ans))
print(*ans)


def ans(k):
	if k == 2 or k == 3:
		return True
	i = 2
	while i * i <= k:
		if k % i == 0:
			return False
		i += 1
	return True
n = int(input())
t = n
if ans(t):
	print(1)
	print(t)
	exit(0)
elif ans(t - 2):
	print(2)
	print('2', t - 2)
	exit(0)
elif ans(t - 3):
	print(2)
	print('3', t - 3)
	exit(0)
elif ans(t - 4):
	print(3)
	print('2', '2', t - 4)
	exit(0)
print(3)
print(5, end=' ')
d = t - 5
for i in range(2, t + 1, 1):
	if ans(i) and ans(d - i):
		print(i, d - i)
		break
print()


def miller_rabin(n):
	if n == 2:
		return True
	if n <= 1 or not n & 1:
		return False
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	d = n - 1
	s = 0
	while not d & 1:
		d >>= 1
		s += 1
	for prime in primes:
		if prime >= n:
			continue
		x = pow(prime, d, n)
		if x == 1:
			continue
		for r in range(s):
			if x == n - 1:
				break
			if r + 1 == s:
				return False
			x = x * x % n
	return True
N = int(input())
if miller_rabin(N):
	print(1)
	print(N)
elif miller_rabin(N - 2):
	print(2)
	print(2, N - 2)
elif miller_rabin(N - 4):
	print(3)
	print(2, 2, N - 4)
else:
	i = 3
	while True:
		if miller_rabin(i):
			if miller_rabin((N - i) // 2):
				print(3)
				print(i, (N - i) // 2, (N - i) // 2)
				break
			elif miller_rabin(N - 2 * i):
				print(3)
				print(i, i, N - 2 * i)
				break
		i += 2


import math
n = int(input())

def isPrime(number):
	flag = True
	if number == 1:
		return False
	for i in range(2, math.floor(math.sqrt(number)) + 1):
		if number % i == 0:
			flag = False
	if flag:
		return True
	else:
		return False
if isPrime(n):
	print(1)
	print(n)
elif isPrime(n - 2):
	print(2)
	print(n - 2, 2)
elif isPrime(n - 3):
	print(n - 3, 3)
else:
	flag2 = True
	i = 3
	while i <= n:
		j = 3
		while j <= n:
			if isPrime(i) and isPrime(j) and isPrime(n - i - j):
				if i + j + (n - i - j) == n:
					flag2 = False
					print(3)
					print(i, j, n - i - j)
					break
			j += 2
		i += 2
		if flag2 == False:
			break


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
from itertools import permutations
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
z = seive(10 ** 4 + 1)
pri = []
for i in range(2, 10 ** 4 + 1):
	if z[i]:
		pri.append(i)
n = int(input())
if n in pri:
	print(1)
	print(n)
	exit()
(x, y, z) = (-1, -1, -1)
for i in range(len(pri)):
	flag = 0
	for j in range(len(pri)):
		z = pri[i] + pri[j]
		if check_prim(n - z):
			x = pri[i]
			y = pri[j]
			z = n - z
			flag = 1
			break
	if flag:
		break
if x != 0 and y != 0 and (z != 0):
	print(3)
	print(x, y, z)
else:
	print(2)
	print(x, y)


def isPrime(x):
	if x == 1:
		return False
	if x == 2:
		return True
	if x % 2 == 0:
		return False
	i = 3
	while i * i <= x:
		if x % i == 0:
			return False
		i += 2
	return True
n = int(input())
if isPrime(n):
	ans = [n]
else:
	bigPrime = 0
	for i in range(n - 1, 0, -1):
		if isPrime(i):
			bigPrime = i
			break
	ans = [bigPrime]
	n -= bigPrime
	if isPrime(n):
		ans.append(n)
	else:
		for i in range(1, n):
			j = n - i
			if isPrime(i) and isPrime(j):
				ans.append(i)
				ans.append(j)
				break
print(len(ans))
for i in ans:
	print(i, end=' ')


def isPrime(n1):
	i = 2
	while i * i <= n1:
		if n1 % i == 0:
			return False
		i += 1
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
elif isPrime(n - 2):
	print(2)
	print(n - 2, 2)
else:
	n -= 3
	for i in range(2, n):
		if isPrime(i) and isPrime(n - i):
			print(3)
			print(3, i, n - i)
			break


def is_prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	for divisor in range(3, int(n ** 0.5) + 1, 2):
		if n % divisor == 0:
			return False
	return True
a = int(input())
if a < 9:
	print(1, a, sep='\n')
else:
	b = a - 6
	while not is_prime(b):
		b -= 2
	c = a - b
	for i in range(1, c, 2):
		if is_prime(i) and is_prime(c - i):
			print(3)
			print(i, c - i, b)
			break


import math
n = int(input())
primes = [2]
for i in range(3, math.ceil(n ** 0.5) + 1):
	for p in primes:
		if i % p == 0:
			break
	else:
		primes.append(i)

def isprime(x):
	if x == 1:
		return False
	for p in primes:
		if x % p == 0 and x > p:
			return False
	else:
		return True
if isprime(n):
	print(1)
	print(n)
else:
	x1 = n
	while not isprime(x1):
		x1 -= 2
	if isprime(n - x1):
		print(2)
		print(x1, n - x1)
	else:
		l = n - x1
		for x2 in primes:
			if isprime(l - x2):
				print(3)
				print(x1, x2, l - x2)
				break
		else:
			print('nu chto podelat...')


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	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

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	n = int(input())
	if is_prime(n):
		print(1)
		print(n)
		return
	ans = []
	i = n
	c = 3
	for i in range(n, 1, -1):
		if is_prime(i):
			ans.append(i)
			n -= i
			break
	for i in range(2, n + 1):
		if is_prime(i) and n - i == 0:
			ans.append(i)
			break
		elif is_prime(i) and is_prime(n - i):
			ans.append(i)
			ans.append(n - i)
			break
	print(len(ans))
	print(*ans)
for _ in range(1):
	solve()


n = int(input())

def snt(n):
	if n < 2:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
x = n
while not snt(x):
	x -= 1
s = n - x
if s == 0:
	print(1, '\n' + str(n))
elif s == 2:
	print(2, '\n2 ' + str(n - 2))
else:
	for i in range(s // 2 + 1):
		if snt(i) and snt(s - i):
			break
	print(3)
	print(i, s - i, x)


import math as m
n = int(input())

def prime(n):
	if n == 1:
		return False
	for j in range(2, int(m.sqrt(n)) + 1):
		if n % j == 0:
			return False
	return True
if prime(n):
	print(1)
	print(n)
else:
	ans = []
	ans.append(3)
	n -= 3
	for j in range(n, 1, -1):
		if prime(j) and prime(n - j):
			ans.append(j)
			ans.append(n - j)
			break
	print(3)
	print(*ans)


def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if not n % i:
			return False
	return True
n = int(input())
ans = []
for i in range(n, -1, -1):
	if is_prime(i):
		ans.append(i)
		n -= i
		break
for i in range(2, n + 1):
	if is_prime(i) and is_prime(n - i):
		ans.append(i)
		if n - i:
			ans.append(n - i)
		break
print(len(ans))
print(*ans)


from math import *

def isPrime(num):
	if num == 1:
		return False
	x = int(sqrt(num))
	for i in range(2, x + 1):
		if num % i == 0:
			return False
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
else:
	i = n // 2
	while i > 1:
		if isPrime(i) and isPrime(n - 2 * i):
			print(3)
			print(i, i, n - 2 * i)
			break
		i = i - 1


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def prime(n):
	if n < 4:
		return n == 2 or n == 3
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(n ** 0.5) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
n = inp()
if prime(n):
	print(1)
	print(n)
elif prime(n - 2):
	print(2)
	print(2, n - 2)
else:
	print(3)
	cur = n - 3
	for i in range(3, n, 2):
		if prime(i) and prime(cur - i):
			print(3, i, cur - i)
			break


from random import randrange

def is_prime(p):
	k = 100
	if p == 2 or p == 3:
		return True
	if p & 1 == 0 or p == 1:
		return False
	phi = p - 1
	d = phi
	r = 0
	while d & 1 == 0:
		d = int(d >> 1)
		r += 1
	for i in range(k):
		a = randrange(2, p - 2)
		exp = pow(a, d, p)
		if exp == 1 or exp == p - 1:
			continue
		for j in range(r - 1):
			exp = pow(exp, 2, p)
			if exp == 1:
				return False
			if exp == p - 1:
				break
		else:
			return False
	return True

def main():
	n = int(input())
	if is_prime(n):
		print(1)
		print(n)
		return
	if is_prime(n - 2):
		print(2)
		print(2, n - 2)
		return
	print(3)
	even = n - 3
	left = 3
	right = even - 3
	for i in range(int(even / 2) + 1):
		if is_prime(left) and is_prime(right):
			print(str(3) + ' ' + str(left) + ' ' + str(right))
			return
		left += 2
		right -= 2
main()


def isprime(number):
	return True if not sum((i for i in range(2, int(number ** 0.5) + 1) if number % i == 0)) else False
(n, terms) = (int(input()), [])
counter = 0
for j in range(n, 1, -1):
	if isprime(j) and n - j not in {2, 3}:
		terms.append(j)
		counter += j
		break
if counter != n:
	rem = n - counter
	for j in range(2, n + 1):
		if isprime(rem - j) and isprime(j):
			terms.append(rem - j)
			terms.append(j)
			break
	print(3, ' '.join(map(str, terms)), sep='\n')
else:
	print(1, counter, sep='\n')


import math
n = int(input())
f = 1
for i in range(2, math.ceil(math.sqrt(n)) + 1):
	if i != n and n % i == 0:
		f = 0
		break
if f:
	print(1)
	print(n)
else:
	for i in range(n - 2, 1, -1):
		p = 1
		for j in range(2, math.ceil(math.sqrt(i)) + 1):
			if j != i and i % j == 0:
				p = 0
				break
		if p:
			num1 = i
			n1 = n - i
			break
	if n1 == 2 or n1 == 3:
		print(2)
		print(n1, n - n1)
	else:
		for i in range(2, n1):
			(p1, p2) = (1, 1)
			for j in range(2, math.ceil(math.sqrt(i)) + 1):
				if j != i and i % j == 0:
					p1 = 0
					break
			if p1:
				for j in range(2, math.ceil(math.sqrt(n1 - i)) + 1):
					if j != n1 - i and (n1 - i) % j == 0:
						p2 = 0
						break
			if p1 and p2:
				print(3)
				print(num1, i, n1 - i)
				break


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys
import math
from math import gcd
import bisect

def isPrime(num):
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			return 0
	return 1
n = int(input())
f = 0
for i in range(n, 0, -1):
	if isPrime(i):
		if i == n:
			print(1)
			print(i)
			f = 1
		elif isPrime(n - i):
			print(2)
			print(i, n - i)
			f = 1
		else:
			for j in range(2, n - 1, 1):
				if isPrime(j) and isPrime(n - i - j):
					print(3)
					print(i, j, n - i - j)
					f = 1
					break
		if f == 1:
			break


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left

def isprime(x):
	if x == 3 or x == 5:
		return 1
	for i in range(2, ceil(sqrt(x) + 1)):
		if x % i == 0:
			return 0
	return 1

def solve():
	n = iin()
	l = []
	z = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983]
	s = set(z)
	x = 0
	while n - 2 * x > 0:
		if isprime(n - 2 * x):
			t = 2 * x
			if t != 0:
				for i in z:
					if t - i == 0:
						l = [n - 2 * x, i]
						break
					elif t - i in s:
						l = [n - 2 * x, i, t - i]
						break
			else:
				l = [n]
			break
		x += 1
	print(len(l))
	print(*l)
qwe = 1
for _ in range(qwe):
	solve()


import math

def is_prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for divisor in range(3, sqr, 2):
		if n % divisor == 0:
			return False
	return True
a = int(input())
if a < 9:
	print(1)
	print(a)
else:
	b = a - 6
	while not is_prime(b):
		b -= 2
	c = a - b
	for i in range(1, c, 2):
		if is_prime(i) and is_prime(c - i):
			print(3)
			print(i, c - i, b)
			break


from sys import *

def prime(a):
	if a < 2:
		return False
	for j in range(2, int(a ** 0.5) + 1):
		if a % j == 0:
			return False
	return True
p = [i for i in range(2, 10000) if prime(i)]
lp = len(p)
n = int(input())
if prime(n):
	print('1\n', n)
	exit()
if n > 3 and prime(n - 2):
	print('2\n', 2, n - 2)
	exit()
if n > 5 and prime(n - 4):
	print('3\n', 2, 2, n - 4)
	exit()
for j in range(lp):
	for i in range(j, lp):
		if p[j] + p[i] + 2 > n:
			break
		if prime(n - p[i] - p[j]):
			print('3\n', p[j], p[i], n - p[i] - p[j])
			exit()


def pr(x):
	if x == 0:
		return True
	if x == 2:
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(x ** (1 / 2)) + 2, 2):
		if x % i == 0:
			return False
	return True
n = int(input())
a = n
while not pr(a):
	a -= 1
n -= a
b = 0
c = 0
for i in range(n):
	if i == 1 or n - i == 1:
		continue
	if pr(i) and pr(n - i):
		b = i
		c = n - i
		break
ans = [a, b, c]
ans.sort(reverse=True)
if ans[2] > 0:
	print(3)
	print(*ans)
elif ans[1] > 0:
	print(2)
	print(*ans[:2])
else:
	print(1)
	print(ans[0])


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if 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 = i + 6
	return True

def main():
	n = int(input())
	if n == 3:
		print(1)
		print(3)
	elif n == 5:
		print(2)
		print(2, 3)
	else:
		i = 3
		while True:
			temp = n - i
			if isPrime(temp // 2):
				print(3)
				print(i, temp // 2, temp // 2)
				break
			i += 2
			while not isPrime(i):
				i += 2
	return

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


p = lambda x: True if sum((x % i == 0 for i in range(2, int(x ** 0.5) + 1))) == 0 else False
n = int(input())
if n in {3, 5}:
	print(1, '\n', n)
	quit()
for i in range(2, 100000):
	j = n - i - 3
	if j > 1 and p(i) and p(j):
		print(3, '\n', 3, i, j)
		quit()


import random

def bpow(a, n, mod):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * a % mod
		a = a * a % mod
		n //= 2
	return res

def is_prime(p):
	if p <= 1:
		return False
	elif p < 4:
		return True
	else:
		for _ in range(10):
			a = random.randint(2, p - 1)
			if bpow(a, p - 1, p) != 1:
				return False
		return True
n = int(input())
p = n
ans = []
while not is_prime(p):
	p -= 1
ans.append(p)
if n - p == 2:
	ans.append(2)
else:
	n -= p
	for i in range(2, n + 1):
		if is_prime(i) and is_prime(n - i):
			ans.append(i)
			ans.append(n - i)
			break
print(len(ans))
for x in ans:
	print(x, end=' ')


def isprime(x):
	if x == 2:
		return 1
	if x % 2 == 0:
		return 0
	i = 3
	while i * i <= x:
		if x % i == 0:
			return 0
		i += 1
	return 1
n = int(input())
if n == 3 or n == 5 or n == 7:
	print(1)
	print(n)
else:
	if n % 2:
		print(3)
		n -= 3
		print(3, end=' ')
	else:
		print(2, end=' ')
	i = 2
	while 1:
		if isprime(i) and isprime(n - i):
			print(i, n - i)
			break
		i += 1


import math

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

def decomposition(even):
	if even == 4:
		return (2, 2)
	for i in range(even - 3, int(math.sqrt(even)) - 1, -2):
		if is_prime(i) and is_prime(even - i):
			return (i, even - i)
n = int(input())
if is_prime(n):
	print(1)
	print(n)
else:
	for i in range(n, 3, -2):
		if is_prime(i):
			if n - i == 2:
				print(2)
				print(i, 2)
				break
			else:
				print(3)
				print(i, *decomposition(n - i))
				break


def isprime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return 0
		i += 1
	return 1
t = 1
for ___ in range(t):
	n = int(input())
	for i in range(n + 1, -1, -1):
		if isprime(i):
			ans = i
			break
	n1 = n - ans
	for i in range(2, n1 + 1):
		if isprime(i) and isprime(n1 - i):
			x = i
			y = n1 - i
			break
	if n == 3:
		print(1)
		print(3)
	elif n == 5:
		print(1)
		print(5)
	elif n1 == 0:
		print(1)
		print(ans)
	elif n1 == 2:
		print(2)
		print(ans, 2)
	else:
		print(3)
		print(ans, x, y)


import math
n = int(input())
p = [0 for _ in range(1001)]
x = 2
p[0] = 1
p[1] = 1
while x * x <= 1001:
	for i in range(2 * x, 1001, x):
		p[i] = 1
	x += 1
pr = 0

def isprime(num):
	for i in range(2, int(math.sqrt(n)) + 1):
		if num % i == 0:
			return False
	return True
e = 0
if isprime(n):
	print(1)
	print(n)
	exit(0)
for k in range(n, 1, -1):
	if isprime(k):
		if (n - k) % 2 == 0:
			pr = n - k
			e = 1
			break
if pr == 2:
	print(2)
	print(2, n - 2)
	exit(0)
for i in range(2, 1001):
	if p[pr - i] == 0 and p[i] == 0:
		print(3)
		print(n - pr, i, pr - i)
		exit(0)


def primes2(limit):
	if limit < 2:
		return []
	if limit < 3:
		return [2]
	lmtbf = (limit - 3) // 2
	buf = [True] * (lmtbf + 1)
	for i in range((int(limit ** 0.5) - 3) // 2 + 1):
		if buf[i]:
			p = i + i + 3
			s = p * (i + 1) + i
			buf[s::p] = [False] * ((lmtbf - s) // p + 1)
	return [2] + [i + i + 3 for (i, v) in enumerate(buf) if v]
n = int(input())
ps = primes2(int(n ** 0.5) + 1)

def solve(n):
	if is_prime(n):
		return [n]
	for m in range(n - 2, n // 3 - 1, -1):
		if is_prime(m):
			r = n - m
			if is_prime(r):
				return [m, r]
			for s in range(r - 2, r // 2 - 1, -1):
				if is_prime(s) and is_prime(r - s):
					return [m, s, r - s]

def is_prime(n):
	sqrt_n = int(n ** 0.5)
	for p in ps:
		if n == p:
			return True
		if n % p == 0:
			return False
		if p > sqrt_n:
			return True
	return True
ans = solve(n)
print(len(ans))
print(*ans)


def main():
	n = int(input())
	if n == 3:
		print(1)
		print(3)
	elif n == 4:
		print(2)
		print(2, 2)
	elif n == 5:
		print(2)
		print(2, 3)
	elif n == 6:
		print(2)
		print(3, 3)
	elif n == 7:
		print(2)
		print(2, 5)
	elif n == 8:
		print(2)
		print(3, 5)
	elif n == 9:
		print(2)
		print(2, 7)
	elif n == 10:
		print(2)
		print(3, 7)
	if n <= 10:
		return
	for i in range(n, -1, -1):
		j = 2
		simple = True
		while j * j <= i:
			if i % j == 0:
				simple = False
			j += 1
		if simple:
			n -= i
			break
	ans = [i]
	prime = [True] * (n + 2)
	prime[0] = False
	prime[1] = False
	for i in range(2, n + 1):
		if prime[i]:
			if i * i <= n:
				for j in range(i * i, n + 1, i):
					prime[j] = False
	i = k = 0
	for i in range(2, n + 1):
		k = n - i
		if prime[i] and prime[k]:
			break
	if i != 0:
		ans.append(i)
	if k != 0:
		ans.append(k)
	print(len(ans))
	for x in ans:
		print(x, end=' ')
main()


def IsPrime(n):
	d = 2
	while d * d <= n and n % d != 0:
		d += 1
	return d * d > n
ans = []
n = int(input())
if n == 3:
	print(1)
	print(3)
elif n == 5:
	print(1)
	print(5)
elif n == 7:
	print(1)
	print(7)
else:
	n -= 3
	ans.append(3)
	for i in range(2, min(n, 9782)):
		if IsPrime(i) and IsPrime(n - i):
			ans.append(i)
			ans.append(n - i)
			break
	print(3)
	print(*ans)


import math

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
if isPrime(n):
	print(1)
	print(n)
elif isPrime(n - 2):
	print(2)
	print('%d %d' % (2, n - 2))
else:
	i = 1
	while not isPrime(n - i):
		i += 1
	j = 2
	while not (isPrime(j) and isPrime(i - j)):
		j += 1
	print(3)
	print('%d %d %d' % (n - i, j, i - j))


from sys import stdin, stderr

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def is_prime(n):
	if n <= 3:
		return True
	for pt in range(2, n):
		if pt * pt > n:
			return True
		if n % pt == 0:
			return False
	return True

def solve(n):
	if is_prime(n):
		return [n]
	for n0 in range(3, n - 3):
		if not is_prime(n0):
			continue
		if not is_prime(n - 3 - n0):
			continue
		return [3, n0, n - 3 - n0]
	return []

def run():
	(n,) = readInts()
	vs = solve(n)
	print(len(vs))
	print(' '.join(map(str, vs)))
run()


import math

def is_prime(a):
	n = math.sqrt(a)
	n = int(n) + 1
	return all((a % i for i in range(2, n)))

def sieves(n):
	size = n // 2
	sieve = [1] * size
	limit = int(n ** 0.5)
	for i in range(1, limit):
		if sieve[i]:
			val = 2 * i + 1
			tmp = (size - 1 - i) // val
			sieve[i + val::val] = [0] * tmp
	return [2] + [i * 2 + 1 for (i, v) in enumerate(sieve) if v and i > 0]
pri = sieves(400)
n = int(input())
for i in range(n, 1, -2):
	if is_prime(i):
		primes = i
		break
ans = []
no = 1
if n == primes:
	ans = [n]
	no = 1
elif primes + 2 == n:
	ans = [2, primes]
	no = 2
else:
	k = n - primes
	for i in pri:
		for j in pri:
			if i + j == k:
				ans = [primes, i, j]
				no = 3
print(no)
for i in ans:
	print(i, end=' ')


import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def isprime(n):
	if n == 1:
		return False
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True
n = read_int()
p = n
ans = []
while not isprime(p):
	p -= 1
ans.append(p)
n -= p
if n > 0:
	if n == 2:
		ans.append(2)
		print(len(ans))
		print(*ans)
	else:
		for i in range(1, n):
			if isprime(i) and isprime(n - i):
				ans.append(i)
				ans.append(n - i)
				break
		print(len(ans))
		print(*ans)
else:
	print(len(ans))
	print(*ans)


def prime(i):
	for k in range(2, int(i ** 0.5) + 1):
		if i % k == 0:
			return False
	return True
x = int(input())
if prime(x):
	print(1)
	print(x)
	quit()
i = x
while not prime(i):
	i -= 2
p1000 = [i for i in range(2, 3000) if prime(i)]
rem = x - i
if rem == 2:
	print(2)
	print(2, i)
	quit()
print(3)
for jj in p1000:
	if rem - jj in p1000:
		print(i, jj, rem - jj)
		quit()


def prime(x):
	if x == 2:
		return True
	if x % 2 == 0:
		return False
	p = 3
	while p * p <= x:
		if x % p == 0:
			return False
		p += 2
	return True
n = int(input())
if prime(n):
	print(1, '\n', n)
elif prime(n - 2):
	print(2, '\n', 2, n - 2)
else:
	x = n - 2
	while not prime(x):
		x -= 2
	n -= x
	for a in range(2, n):
		if prime(a) and prime(n - a):
			print(3, '\n', x, a, n - a)
			break


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
ans = [3]
n -= 3
primes = []
M = 10001
p = [1] * M
for i in range(2, M):
	if p[i]:
		primes.append(i)
		for j in range(2 * i, M, i):
			p[j] = 0

def is_prime(x):
	for i in range(2, int(x ** 0.5) + 1):
		if not x % i:
			return False
	return True
if n:
	for i in primes:
		if n - i == 0:
			ans.append(i)
			break
		if is_prime(n - i):
			ans.append(i)
			ans.append(n - i)
			break
print(len(ans))
print(*ans)


from math import *

def estpremier(n):
	if n < 7:
		if n in (2, 3, 5):
			return True
		else:
			return False
	if n & 1 == 0:
		return False
	k = 3
	r = int(sqrt(n)) + 1
	while k <= r:
		if n % k == 0:
			return False
		k += 2
	return True
n = int(input())
if estpremier(n):
	print(1)
	print(n)
else:
	bb = True
	m = (n + 1) // 2
	z = 1000
	i = max(2, m - z)
	while bb and i < m + 1:
		if estpremier(i):
			j = n - i
			if estpremier(j):
				bb = False
				print(2)
				print(i, j)
		i += 1
	if bb:
		m = (n + 1) // 3
		z = 1000
		i = max(2, m - z)
		while bb and i < m + 1:
			if estpremier(i):
				j = i
				while bb and j < m + z:
					if estpremier(j):
						k = n - i - j
						if estpremier(k):
							bb = False
							print(3)
							print(i, j, k)
					j += 1
			i += 1


def prm(n):
	i = 2
	n = int(n)
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
a = int(input())
if prm(a):
	print('1')
	print(a)
else:
	a -= 3
	b = 3
	while True:
		if prm(b):
			if prm(a - b):
				print(3)
				print('3 ', b, ' ', a - b)
				break
		b += 2


gap = 300
m = 1 << 15
isp = [False] * 2 + [True] * (m - 1)
ps = []
for i in range(2, m + 1):
	if isp[i]:
		ps.append(i)
		for j in range(i * i, m + 1, i):
			isp[j] = False
n = int(input())
assert n % 2
if n >= m:
	low = n - gap
	ispg = [True] * (gap + 1)
	for p in ps:
		for i in range((low - 1) // p + 1, n // p + 1):
			ispg[i * p - low] = False

def is_prime(k):
	return isp[k] if k <= m else ispg[k - low]
p = n
while not is_prime(p):
	p -= 2
s = [p]
if p != n:
	if n - p == 2:
		s += [n - p]
	else:
		q = 2
		while not (is_prime(q) and is_prime(n - p - q)):
			q += 1
		s += [q, n - p - q]
print(len(s))
print(*s)


def isPrime(x):
	if x == 1:
		return 0
	el = 2
	while el * el <= x:
		if x % el == 0:
			return 0
		el += 1
	return 1
n = int(input())
if n % 2 == 1:
	if isPrime(n):
		print(1)
		print(n)
	else:
		n1 = n
		while isPrime(n1) == 0 or n - n1 < 4:
			n1 -= 1
		print(3)
		n2 = n - n1
		while isPrime(n2) == 0 or isPrime(n - n1 - n2) == 0:
			n2 -= 1
		print(n1, n - n1 - n2, n2)
else:
	n1 = n
	while isPrime(n1) == 0 or isPrime(n - n1) == 0:
		n1 -= 1
	print(2)
	print(n - n1, n1)


import math

def prime(n):
	if n == 1:
		return False
	else:
		for i in range(2, math.ceil(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def two(n):
	for i in range(n // 2 + 1):
		if prime(i) and prime(n - i):
			return True
	return False
n = int(input())
if prime(n):
	print(1)
	print(n)
elif prime(n - 2):
	print(2)
	print(n - 2, 2)
else:
	j = 1
	for i in range(2, n // 3 + 1):
		if prime(i) and two(n - i):
			print(3)
			j = i
			break
	r = 1
	for i in range(2, (n - j) // 2 + 1):
		if prime(i) and prime(n - i - j):
			r = i
			break
	print(j, r, n - r - j)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192
from random import random

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def primes(n):
	sieve = [True] * n
	for i in range(2, n):
		if sieve[i]:
			for j in range(i * i, n, i):
				sieve[j] = False
	return [i for i in range(3, n, 2) if sieve[i]]
P = primes(100000)

def is_Prime(X):
	for p in P:
		if p > int(X ** 0.5):
			return True
		if X % p == 0:
			return False

def solve():
	N = getInt()
	if N < 9:
		print(1)
		print(N)
		return
	ans = [3]
	N -= 3
	for p in P:
		if is_Prime(N - p):
			ans += [p, N - p]
			break
	print(3)
	print(*ans)
	return
solve()


import math
n = int(input())

def prime(p):
	if p == 1:
		return False
	fl = True
	for i in range(2, math.ceil(p ** 0.5) + 1):
		if p % i == 0:
			fl = False
	return fl

def sum_of_primes(k):
	fl = True
	for i in range(k // 2 + 1):
		if prime(i) and prime(k - i):
			fl = True
			break
	return fl
if prime(n):
	print(1)
	print(n)
elif prime(n - 2):
	print(2)
	print(2, n - 2)
else:
	l = 1
	for i in range(2, n // 3 + 1):
		if prime(i) and sum_of_primes(n - i):
			l = i
			break
	print(3)
	r = 1
	for k in range((n - l) // 2):
		if prime(k) and prime(n - l - k):
			r = k
			break
	print(l, r, n - l - r)


from sys import stdin as si
from math import sqrt
from collections import Counter as c
import re

class Solution:

	def __init__(self):
		self.lst = []

	def is_prime(self, a):
		return all((a % i for i in range(2, int(a ** 0.5) + 1)))

	def bazinga(self, m):
		if m == 1 or (m > 1 and len(self.lst) == 3):
			return False
		if m == 0:
			print(len(self.lst))
			print(str(self.lst).replace(']', '').replace('[', '').replace(',', ''))
			exit(0)
		for i in range(m, 1, -1):
			if self.is_prime(i):
				self.lst.append(i)
				if not self.bazinga(m - i):
					self.lst.pop(-1)
m = int(si.readline().strip())
S = Solution()
S.bazinga(m)


def is_prime(n):
	if n < 2:
		return False
	d = 2
	while d * d <= n:
		if n % d == 0:
			return False
		d += 1
	return True
n = int(input())
assert n % 2
p = n
while not is_prime(p):
	p -= 2
s = [p]
if p != n:
	if n - p == 2:
		s += [n - p]
	else:
		q = 2
		while not (is_prime(q) and is_prime(n - p - q)):
			q += 1
		s += [q, n - p - q]
print(len(s))
print(*s)


def check(n):
	d = 2
	while d * d <= n:
		if n % d == 0:
			return False
		d += 1
	return True
n = int(input())
flag = False
if check(n) and n > 10:
	print(1, '\n', n)
elif n >= 9:
	Ans = [3]
	n -= 3
	for i in range(2, n):
		if check(i) and check(n - i):
			print(3)
			print(3, i, n - i)
			break
elif n == 3:
	print(1, '\n', 3)
elif n == 5:
	print(1, '\n', 5)
elif n == 7:
	print(1, '\n', 7)


l = list()

def prime(N):
	count = 0
	i = 1
	while i * i <= N:
		if i * i == N:
			count = count + 1
		elif N % i == 0:
			count = count + 2
		if count > 2:
			return 0
		i = i + 1
	if count == 2:
		return 1
	else:
		return 0
n = int(input())
if n % 2 == 0:
	for j in range(2, n):
		s = prime(j)
		t = prime(n - j)
		if s == 1 and t == 1:
			l.append(j)
			l.append(n - j)
			break
else:
	l.append(3)
	if n - 3 == 0:
		l = [3]
	elif n - 3 > 2:
		n = n - 3
		for j in range(2, n):
			s = prime(j)
			t = prime(n - j)
			if s == 1 and t == 1:
				l.append(j)
				l.append(n - j)
				break
	else:
		l = [5]
		n = n - 5
		if n > 2:
			for j in range(2, n):
				s = prime(j)
				t = prime(n - j)
				if s == 1 and t == 1:
					l.append(j)
					l.append(n - j)
					break
print(len(l))
print(*l)


from math import *
n = int(input())

def prime(x):
	for i in range(2, ceil(sqrt(x)) + 1):
		if x % i == 0:
			return 0
	return 1
if prime(n) != 0:
	print('1')
	print(n)
else:
	for i in range(2, n):
		if prime(i) != 0:
			for j in range(n - i, 2, -1):
				if prime(j) != 0:
					c = n - i - j
					if c == 0:
						print('2')
						print(i, j)
						quit()
					elif c != 1:
						if prime(n - i - j) != 0:
							print('3')
							print(i, j, c)
							quit()


from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

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

def main():
	n = ii()
	if isprime(n):
		print(1)
		print(n)
		exit(0)
	for i in range(n - 1, 1, -1):
		if isprime(i):
			if isprime(n - i):
				print(2)
				print(i, n - i)
				exit(0)
			else:
				x = n - i
				for j in range(x - 1, 1, -1):
					if isprime(j) and isprime(x - j):
						print(3)
						print(i, j, x - j)
						exit(0)
main()

def main():
	n = ii()
main()


def is_p(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	return True
n = int(input())
ans = []
for i in range(n, -1, -1):
	if is_p(i):
		ans += [i]
		n -= i
		break
for i in range(2, n + 1):
	if is_p(i) and is_p(n - i):
		ans.append(i)
		if n - i != 0:
			ans.append(n - i)
		break
print(len(ans))
print(*ans)


from math import sqrt
from itertools import count, islice

def isPrime(n):
	if n < 2:
		return False
	return all((n % i for i in islice(count(2), int(sqrt(n) - 1))))
number = int(input())
if number < 9:
	print(1)
	print(number)
else:
	number2 = number - 6
	while not isPrime(number2):
		number2 -= 2
	difference = number - number2
	for i in range(1, difference, 2):
		if isPrime(i) and isPrime(difference - i):
			print(3)
			print(' '.join(map(str, [i, difference - i, number2])))
			break


from math import sqrt

def is_prime(a):
	for i in range(2, int(sqrt(a)) + 2):
		if a % i == 0:
			return False
	return True
n = int(input())
if is_prime(n):
	print('1')
	print(n)
else:
	for a in range(2, n):
		if is_prime(a):
			for b in range(n - a, 2, -1):
				if is_prime(b):
					c = n - a - b
					if c == 0:
						print('2')
						print(a, b)
						exit()
					elif c != 1:
						if is_prime(n - a - b):
							print('3')
							print(a, b, c)
							exit()


import math

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

def solve():
	(n,) = map(int, input().split())
	if is_prime(n):
		print(1)
		print(n)
		return
	number = n
	while not is_prime(number):
		number -= 1
	n -= number
	if is_prime(n):
		print(2)
		print(number, n)
		return
	for i in range(2, n):
		if is_prime(i) and is_prime(n - i):
			print(3)
			print(number, i, n - i)
			return
t = 1
for _ in range(t):
	solve()


import math

def Prost(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	else:
		return True
n = int(input())
r = 0
if Prost(n):
	print(1)
	print(n)
else:
	for i in range(n - 1, n - 300, -1):
		if Prost(i):
			r = i
			break
	k = n - r
	if k == 2:
		print(2)
		print(r, k)
	else:
		for i in range(2, k):
			if Prost(i) and Prost(k - i):
				print(3)
				print(r, i, k - i)
				break


import math
n = int(input())
primes = [True] * 301
real = set()
for i in range(2, 301):
	if primes[i]:
		real.add(i)
		for j in range(i * i, 301, i):
			primes[j] = False
lastp = n
for i in range(n, n - 300, -1):
	flag = 0
	for j in range(2, int(math.sqrt(i)) + 1):
		if i % j == 0:
			flag = 1
			break
	if flag == 0:
		lastp = i
		break
if lastp == n:
	print(1)
	print(n)
elif lastp == n - 2:
	print(2)
	print(2, n - 2)
else:
	n = n - lastp
	print(3)
	for x in real:
		if n - x in real:
			print(x, n - x, lastp)
			break