Implementing Euler's Totient Function (Phi Function) in Go

Euler's totient function, denoted as $\phi(n)$, counts the number of positive integers up to a given integer $n$ that are relatively prime to $n$. Two integers are relatively prime if their greatest common divisor (GCD) is 1. This function is fundamental in number theory and cryptography, particularly in RSA encryption. Your task is to implement an efficient function to calculate $\phi(n)$ in Go.

Problem Description

You need to create a Go function phi(n int) that takes a positive integer n as input and returns the count of positive integers $k$ such that $1 \le k \le n$ and $\text{gcd}(k, n) = 1$.

Requirements:

1. Function Signature: The function must have the signature func phi(n int) int.
2. Correctness: The function must accurately calculate Euler's totient function for any valid positive integer input.
3. Efficiency: For larger inputs, the calculation should be reasonably efficient. A naive approach of iterating through all numbers from 1 to $n$ and calculating GCD will likely be too slow. Consider using the properties of the totient function.
4. Handling Edge Cases: The function should correctly handle the smallest valid input.

Expected Behavior:

• For an input n, the function should return the number of integers $k$ where $1 \le k \le n$ and $\text{gcd}(k, n) = 1$.

Edge Cases:

• What is $\phi(1)$? (Hint: The only positive integer $\le 1$ is 1. Is $\text{gcd}(1, 1) = 1$?)

Examples

Example 1:

Input: 10
Output: 4
Explanation: The positive integers less than or equal to 10 are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
The integers relatively prime to 10 are {1, 3, 7, 9} because:
gcd(1, 10) = 1
gcd(2, 10) = 2
gcd(3, 10) = 1
gcd(4, 10) = 2
gcd(5, 10) = 5
gcd(6, 10) = 2
gcd(7, 10) = 1
gcd(8, 10) = 2
gcd(9, 10) = 1
gcd(10, 10) = 10
There are 4 such numbers.

Example 2:

Input: 7
Output: 6
Explanation: 7 is a prime number. All numbers from 1 to 6 are relatively prime to 7.
gcd(1, 7) = 1
gcd(2, 7) = 1
gcd(3, 7) = 1
gcd(4, 7) = 1
gcd(5, 7) = 1
gcd(6, 7) = 1
gcd(7, 7) = 7
There are 6 such numbers.

Example 3:

Input: 1
Output: 1
Explanation: The only positive integer less than or equal to 1 is 1. gcd(1, 1) = 1. So, there is 1 such number.

Constraints

• $1 \le n \le 10^9$ (The input integer $n$ will be within this range.)
• The input n will be a positive integer.
• Your solution should be able to compute $\phi(n)$ for $n$ up to $10^9$ within a reasonable time limit (e.g., a few seconds).

Notes

• Mathematical Formula: A key property of Euler's totient function is its multiplicative property and its formula based on prime factorization. If the prime factorization of $n$ is $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then: $\phi(n) = n \prod_{i=1}^{k} (1 - \frac{1}{p_i}) = n \frac{p_1-1}{p_1} \frac{p_2-1}{p_2} \cdots \frac{p_k-1}{p_k}$. This can be rewritten as $\phi(n) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdots$. Or, more conveniently for integer arithmetic: $\phi(n) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdots = (p_1^{a_1} \cdots p_k^{a_k}) \frac{p_1-1}{p_1} \cdots \frac{p_k-1}{p_k}$ $= (p_1^{a_1-1} (p_1-1)) \cdots (p_k^{a_k-1} (p_k-1))$. A computationally friendly way is to start with result = n and for each distinct prime factor p of n, update result = result - result / p.

• Prime Factorization: To use the formula, you'll need an efficient way to find the distinct prime factors of n. You can iterate up to $\sqrt{n}$ to find these factors.

• Integer Division: Be mindful of integer division in Go. Ensure intermediate calculations don't lose precision.

• GCD Function: While you won't directly use a GCD function for the efficient solution, understanding GCD is crucial for grasping the definition of Euler's totient function.