import more_itertools as mit
import itertools

# https://stackoverflow.com/questions/46841968/fastest-way-of-testing-if-a-number-is-prime
def FirstPrimeFactor(n):
    if n & 1 == 0:
        return 2
    d= 3
    while d * d <= n:
        if n % d == 0:
            return d
        d= d + 2
    return n

def is_prime(x):
    if x==1:
        return False
    return FirstPrimeFactor(x)==x

lst = list(range(1,9+1))

def list_of_numbers_to_str(l):
    return "".join(map(str, l))

def is_even(x):
    return x&1 == 1
    
for p in itertools.permutations(lst):
    if is_even(list(p)[-1]):
        print (f"permutation {p}")
        # https://stackoverflow.com/questions/19368375/set-partitions-in-python
        for x in [part for k in range(1, len(p) + 1) for part in mit.set_partitions(p, k)]:
            list_of_strings=list(map(list_of_numbers_to_str, x))
            if all(map(is_prime, map(int, list_of_strings))):
                print(f"OK {sorted(list_of_strings)}")