Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?
The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
 The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.  

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.  

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.