// Arup Guha
// 12/2/2022
// Written in CIS 3362 Class
// Solution to FE Review Problem #6: Efficient Phi Function

#include <stdio.h>

int phi(int n) {

    // Set up our accumulators.
    int curN = n;
    int curPhi = n;

    // Our potential divisor.
    int div = 2;

    // Loop until we know we're left with a single prime, at most.
    while (div*div <= curN) {

        // Divides out copies of div.
        int flag = 0;
        while (curN%div == 0) {
            flag = 1;
            curN /= div;
        }

        // Update phi if necessary.
        if (flag) curPhi = curPhi/div*(div-1);

        // Go to the next.
        div++;
    }

    // Case where a prime is left over.
    if (curN>1)
        curPhi = curPhi/curN*(curN-1);

    // Ta da!
    return curPhi;
}

int main(void) {

    // Some tests...
    for (int i=2; i<=50; i++)
        printf("%d %d\n", i, phi(i));
    printf("300 %d\n", phi(300));
    return 0;
}