Given a natural number \(n <= 10^9,\) determine the number of natural numbers less than \(n\ ) and coprime to \(n\). This number is denoted by \( f(n) \) and is called Euler's phi function. The complexity of the algorithm should be \( O(\sqrt{n})\) .