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.