Daily-coding-problem #101

# This problem was asked by Alibaba.

# Given an even number (greater than 2), return two prime numbers whose sum will be equal to the given number.


def is_prime(n, primes):
    for p in primes:
        if n == p:
            return True
        if not n%p == 0:
            return False
    return True


def get_primes(num):
    limit = num//2
    primes = list()
    candidates = list()
    for i in range(2, limit+1):
        if is_prime(i, primes):
            primes.append(i)
            candidates.append((i, num-i))
    new_candidates = list()
    for p1, p2 in candidates[::-1]:
        if is_prime(p2, primes):
            primes.append(p2)
            new_candidates.append((p1, p2))
    return new_candidates[-1]


print(4, get_primes(4))
print(10, get_primes(10))
print(100, get_primes(100))       
# assert get_primes(4) == (2, 2)
# assert get_primes(10) == (3, 7)
# assert get_primes(100) == (3, 97)