Factoriality testing algorithms and their efficiency
Notice that the input size is $n = \lceil \log_2 P \rceil$. The problem can be solved in time near linear in $n$, i.e. in time $n \log^{O(1)} n = (\log P)(\log \log P)^{O(1)}$. 

The trick is to do binary search on the integers in $[1, 2\log_2 P]$ in order to find the largest $N$ such that $N! \leq P$: call this number $N(P) = \max\{N: N! \leq P\}$. If $N(P) = P$, the answer is 'yes', otherwise it is 'no'. 

Let us first show that $N(P) \leq 2\log_2 P$ for $P \geq 4$ (for smaller $P$ you can use a lookup table). This follows because for every $N$, $N! \geq (N/2)^{N/2}$, and therefore
$$
\log_2 P \geq \frac{N}{2}\log_2 \frac{N}{2} \geq \frac{N}{2}.
$$

The complexity is $T(2\log_2 P) \cdot O(\log \log P)$, whete $T(N!)$ is the complexity of computing $N!$. This is because the binary search performs $O(\log \log P)$ steps, and at each step computes $N!$ for some $N \leq 2\log_2 P$. The work by Borwein, referenced in Chad's answer, gives a near-linear in $N$ bound on $T(N)$.