# Arup Guha
# 10/19/2020
# Solution to CIS 3362 Homework #5 Problem 5

# Returns true iff n is prime.
def getSmallestNonTrivialDivisor(n):

    i = 2

    # We can stop at the square root.
    while i*i <= n:

        # Found a divisor.
        if n%i == 0:
            return i

        # Try the next value.
        i += 1

    # If we get here, it's prime, so no trivial divisors.
    return -1

# Returns true iff a is a primitive root mod p, assuming p is prime.
def isPrimRoot(a,p):

    cur = 1

    # Multiply a p-2 times.
    for i in range(p-2):
        cur = (cur*a)%p

        # This means we hit 1 too early, not a primitive root.
        if cur == 1:
            return False

    # If we get here we are good.
    return True

def main():

    # Read input and get smallest non-trivial divisor.
    n = int(input("Enter n.\n"))
    div = getSmallestNonTrivialDivisor(n)

    # Non-prime case.
    if div != -1:
        print(n," is not prime. Its smallest non-trivial divisor is ",div,".", sep ="")

    # Prime - get primitive roots.
    else:

        # Beginning greeting.
        print(n,"is prime.")
        print("Its primitive roots are:", end="")

        # Go through all possible primitive roots, and print the ones that pass the test!
        for i in range(2,n):
            if isPrimRoot(i,n):
                print(" ", i, sep="", end="")

#Run it!
main()