# Task
We know that some numbers can be split into two primes. ie. `5 = 2 + 3, 10 = 3 + 7`. But some numbers are not. ie. `17, 27, 35`, etc.. 

Given a positive integer `n`. Determine whether it can be split into two primes. If yes, return the maximum product of two primes. If not, return `0` instead.

# Input/Output

`[input]` integer `n`

A positive integer. 

`0 ≤ n ≤ 100000`

`[output]` an integer

The possible maximum product of two primes. or return `0` if it's impossible split into two primes.

# Example

For `n = 1`, the output should be `0`.

`1` can not split into two primes

For `n = 4`, the output should be `4`.

`4` can split into two primes `2 and 2`. `2 x 2 = 4`

For `n = 20`, the output should be `91`.

`20` can split into two primes `7 and 13` or `3 and 17`. The maximum product is `7 x 13 = 91`

Difficulty: EASY
Tags: Fundamentals

Starter code:
def prime_product(n):
	

Solutions:
def isPrime(n):
	return n == 2 or (n > 2 and n & 1 and all((n % p for p in range(3, int(n ** 0.5 + 1), 2))))

def prime_product(n):
	return next((x * (n - x) for x in range(n >> 1, 1, -1) if isPrime(x) and isPrime(n - x)), 0)


def prime_product(n):

	def is_prime(n):
		return n == 2 or (n > 2 and n % 2 and all((n % d for d in range(3, int(n ** 0.5) + 1, 2))))
	for i in range(n // 2, 1, -1):
		if is_prime(i) and is_prime(n - i):
			return i * (n - i)
	return 0


def primes_set():
	(primes, sieve) = ({2}, [True] * 50000)
	for i in range(3, 317, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((100000 - i * i - 1) // (2 * i) + 1)
	primes.update((2 * i + 1 for i in range(1, 50000) if sieve[i]))
	return primes
primes = primes_set()

def prime_product(n):
	if n % 2 or n == 4:
		return 2 * (n - 2) if n - 2 in primes else 0
	(m, s) = (n // 2, n % 4 == 0)
	return next(((m + i) * (m - i) for i in range(s, m, 2) if {m + i, m - i} < primes), 0)


def prime_product(n):
	result = 0

	def is_prime(num):
		for i in range(2, int(num ** 0.5) + 1):
			if num % i == 0:
				return False
		return True
	for i in range(2, n // 2 + 1):
		if is_prime(i) and is_prime(n - i):
			result = i * (n - i)
	return result


from itertools import compress
import numpy as np
from bisect import bisect
xs = np.ones(300000)
xs[:2] = 0
xs[4::2] = 0
for i in range(3, int(len(xs) ** 0.5) + 1):
	if xs[i]:
		xs[i * i::i] = 0
primes = list(compress(range(len(xs)), xs))

def iter_primes(n):
	i = bisect(primes, n // 2)
	for x in range(2, primes[i] + 1):
		if xs[x] and xs[n - x]:
			yield (x, n - x)

def prime_product(n):
	return max((a * b for (a, b) in iter_primes(n)), default=0)


def prime_product(n, sieve=[False, False, True, True]):
	for x in range(len(sieve), n + 1):
		sieve.append(x % 2 and all((x % p for p in range(3, int(x ** 0.5) + 1, 2) if sieve[p])))
	return next((p * (n - p) for p in range(n // 2, 1, -1) if sieve[p] and sieve[n - p]), 0)


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

def prime_product(n):
	for i in range(n // 2 + 1)[::-1]:
		if is_prime(i) and is_prime(n - i):
			return i * (n - i)
	return 0


from bisect import bisect

def prime_product(n):
	bisect_point = bisect(primes, n // 2)
	if n % 2:
		return 2 * (n - 2) if n - 2 in prime_set else 0
	for prime in primes[:bisect_point][::-1]:
		if n - prime in prime_set:
			return prime * (n - prime)
	return 0

def get_primes(n):
	primes = [True] * (n + 1)
	for num in range(2, int(n ** 0.5) + 1):
		if primes[num]:
			primes[num * 2::num] = [False] * len(primes[num * 2::num])
	return [i for (i, x) in enumerate(primes) if x and i > 1]
max_input = 100000
primes = get_primes(max_input)
prime_set = set(primes)


LIMIT = 100000
sieve = [True] * (LIMIT // 2)
for n in range(3, int(LIMIT ** 0.5) + 1, 2):
	if sieve[n // 2]:
		sieve[n * n // 2::n] = [False] * ((LIMIT - n * n - 1) // 2 // n + 1)
PRIMES_LIST = [2] + [2 * i + 1 for i in range(1, LIMIT // 2) if sieve[i]]
PRIMES = set(PRIMES_LIST)
del sieve
from bisect import bisect

def prime_product(n):
	if n % 2:
		return 2 * (n - 2) if n - 2 in PRIMES else 0
	for p in PRIMES_LIST[:bisect(PRIMES_LIST, n // 2)][::-1]:
		if n - p in PRIMES:
			return (n - p) * p


def prime_product(n):

	def prime(a):
		if a == 2:
			return True
		if a < 2 or a % 2 == 0:
			return False
		return not any((a % x == 0 for x in range(3, int(a ** 0.5) + 1, 2)))
	if n <= 3:
		return 0
	i = n // 2
	while i > 0:
		if prime(n - i) and prime(i):
			return (n - i) * i
		i -= 1
	return 0