Write a method totient that returns \(\phi(n)\).

Question

By convention, \(\phi(1)=1\) . For \(n \geq 2\), you must use Euler's formula \(\phi(n) = (p_1-1)p_1^{e_1-1} \cdot (p_2-1)p_2^{e_2-1} \dots (p_k-1)p_k^{e_k-1}\) for \(n=p_1^{e_1} \cdot p_2^{e_2} \dots p_k^{e_k}\). Your solution will not receive full credit if you count the number of integers below n that are relatively prime with n by "brute force". Call the smallestPrimeFactor method from Part (a). Assume that it works correctly, regardless of what you wrote in Part (a). Solutions that include code that can be replaced by a call to smallestPrimeFactor will not receive full credit.

Complete the method totient below.

Answer 1

Ooh, a fun one! I'm probably answering this long after it was useful in your class, but I'll write an answer for posterity, maybe.

Ok, here's the logic of the solution: For a given n we want to know its smallest prime factor, so that we can accumulate (p1-1)^(e_1-1) into an accumulator variable (which is initialized at 1 so that it can accumulate via multiplication). Now that we have used up the factor p1 in n, we want to "throw it away and move to the next". Therefore we divide n by p_1^e_1 to eliminate all factors of p_1 from n.

Repeat until the variable tracking what remains of n becomes 1.

public static int totient(int n) {

// Initialize a smallest prime factor, initially pi = p1

int pi = smallestPrimeFactor(n);

// Initialize an accumulator variable which will accumulate to the totient of n.

int totient = 1;

while (n > 1) {

// Find ei, which is the exponent in the prime factorization.

ei = 1;

while (n/pi % pi == 0) {

ei += 1;

n /= pi;

}

// Update the totient.

totient *= Math.pow(pi-1, ei-1);

}

return totient;

}