The following algorithm decides if a number $n>0$ is a totient or a nontotient:
if n = 1 return true if n is odd return false for k in n..n^2 if φ(k) = n return true return false
This is very slow; even using a sieve it takes $n^2$ steps to decide that $n$ is nontotient. Is there a fast method? Polynomial (in $\log n$) would be best but is probably too much to hope for.
Edit: I was able to adapt this
totient(n,m=1)={ my(k,p); if(n<2,return(n==1)); if(n%2,return(0)); fordiv(n,d, if(d
from Max Alekseyev's $\varphi^{-1}$ script, which is substantially faster than the pseudocode above.