integer_partition_ways.py

def partition(n):
    # x: current coin, y: remain value
    def helper(x, y):
        if y <= 0:
            return int(y == 0)
        # use x and not use x
        z = helper(x, y-x)
        if x < y:
            z += helper(x+1, y)
        return z
    return helper(1, n)

if __name__ == '__main__':
    ans = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, \
     56, 77, 101, 135, 176, 231, 297, 385, 490]
    for i, p in enumerate(ans):
        assert partition(i) == p

Only prime

def is_prime(p):
    if p < 2:
        return False
    for x in range(2, int(p**0.5)+1):
        if p%x == 0:
            return False
    return True

def only_prime(lst):
    return sum([is_prime(i) for i in lst]) == len(lst)

def only_one_odd(lst):
    return sum([i%2 for i in lst]) == 1

def help(n)->list:
    ans = set()
    z = (n,)
    if only_prime(z):
        ans.add(z)
    for x in range(1, n):
        for y in help(n - x):
            z = (x,) + y
            if only_prime(z):
                ans.add(tuple(sorted(z)))
    return ans

def solution(n):
    ans = help(n)
    for x in sorted(ans):
        print(n, '=', '+'.join([str(i) for i in x]), sep='')

solution(3)
solution(5)
solution(9)

Result:

3=3
5=2+3
5=5
9=2+2+2+3
9=2+2+5
9=2+7
9=3+3+3