# 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: introductory

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**.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 ** .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 ** .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 is odd then pair must be (2, n - 2) or nothing. This is because 2 is the
    # only even prime and to get an odd number you must add even + odd.
    if n % 2:
        return 2 * (n - 2) if n - 2 in prime_set else 0

    # Check half of prime list (starting from the middle). Return product of first pair found.
    for prime in primes[:bisect_point][::-1]:
        if n - prime in prime_set:
            return prime * (n - prime)

    return 0  # Return 0 if no valid pair found.


def get_primes(n):
    """Sieve of Eratosthenes to calculate all primes less than or equal to n.

    Return set of primes.
    """
    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]


# Calculate all primes up to max but only calculate primes once. Then reference master prime list in all test cases.
max_input = 100000
primes = get_primes(max_input)
prime_set = set(primes)

# generate 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