Here is a little more detail to axn's hint.
If n is prime then \(\phi(n)=n1>n\sqrt{n}\) since n>1.
If n is not prime then n=km for some integers k,m with 1<k<n and 1<m<n.
At least one of k and m is greater than or equal to \(\sqrt{n}\) and we may choose the names so that \(k\geq\sqrt{n}\).
Now \(\phi(n)\) equals the number of integers in the list 0,1,2,,...,n1 which have no factor in common with n.
How many numbers in the list are multiples of m?
