45G - Prime Problem - CodeForces Solution

def is_prime(val):
    if val <= 1:
        return False

    if val == 2:
        return True

    if (val & 1) == 0:
        return False

    d = 3
    while d*d <= val:
        if val % d == 0:
            return False
        d += 2
    return True

n = (int(input()))
f = [1]*(n+1)

def devide2prime(val):
    for i in range(2, n+1):
        if f[i] == 1 and is_prime(i) and is_prime(val - i):
            f[i] = 2
            return

tot = (n+1) * n // 2

def solve():
    if is_prime(tot):
        return

    if tot % 2 == 0:
        devide2prime(tot)
    else:
        if is_prime(tot - 2):
            f[2] = 2
            return

        f[3] = 3
        devide2prime(tot - 3)

solve()
for i in range(1, n+1):
    print(f[i], end = " ")