// Arup Guha
// 10/23/2024
// Solution to Fall 2024 CIS 3362 Quiz 4 Problem 7

#include <stdlib.h>
#include <stdio.h>

int* getRelPrime(int n, int* szPtr) {

    // Allocate space for array, assume everything is initially relatively prime to n.
    int* relprime = malloc(sizeof(int)*n);
    for (int i=0; i<n; i++) relprime[i] = 1;

    // Try to find ALL divisors.
    for (int i=2; i<n; i++)

        // We found one!
        if (n%i == 0)

            // Hit all non-negative multiples of i. (Set to 0.)
            for (int j=0; j<n; j+=i)
                relprime[j] = 0;

    // Will store answer here.
    int* res = calloc(n,sizeof(int));
    *szPtr = 0;

    // Go through all, copy over into res if relatively prime.
    for (int i=0; i<n; i++)
        if (relprime[i])
            res[(*szPtr)++] = i;

    // Reallocate the space for the array and return it.
    res = realloc(res, sizeof(int)*(*szPtr));
    return res;
}

int main() {

    int phi;
    int* vals = getRelPrime(45, &phi);

    for (int i=0; i<phi; i++)
        printf("%d ", vals[i]);
    printf("\n");
    return 0;
}