// Arup Guha
// 10/24/2020
// Solution to CIS 3362 Homework #5 Problem 5 in C, transcribed from Python

#include <stdio.h>

// If n is prime, -1 is returned. Otherwise the smallest divisor of ngreater than 1 is returned.
int getSmallestNonTrivialDivisor(int n) {

    int 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 1 iff a is a primitive root mod p, assuming p is prime, and 0 otherwise.
int isPrimRoot(int a,int p) {

    int cur = 1;

    // Multiply a p-2 times.
    for (int i=0; i<p-2; i++) {
        cur = (cur*a)%p;

        // This means we hit 1 too early, not a primitive root.
        if (cur == 1)
            return 0;
    }

    // If we get here we are good.
    return 1;
}

int main(void) {

    // Read input and get smallest non-trivial divisor.
    int n;
    printf("Enter n.\n");
    scanf("%d", &n);
    int div = getSmallestNonTrivialDivisor(n);

    // Non-prime case.
    if (div != -1)
        printf("%d is not prime. Its smallest non-trivial divisor is %d.\n",n, div);

    // Prime - get primitive roots.
    else {

        // Beginning greeting.
        printf("%d is prime.\n", n);
        printf("Its primitive roots are:");

        // Go through all possible primitive roots, and print the ones that pass the test!
        for (int i=2; i<n; i++)
            if (isPrimRoot(i,n))
                printf(" %d", i);
        printf("\n");
    }

    return 0;
}