Case 1: All digits equal to $1$. One solution is $11$. We rule out $1$, $111$ as it is divisible by $3$, and $1111$ which is divisible by $11$.

In all other cases there is at least one zero. Zeros are not allowed in the leading position, or in the final position (multiples of $10$ are non-prime). Thus there are non-zero digits in the (separate) first and last positions and the one in the last position must be odd.

There must be at least one digit $1$: otherwise the non-zero digits are at least $2$ and $3$, giving a five-digit number which is too large. In particular, there are at least three digits, in fact exactly four digits since if the digit sum is $3$, the number is divisible by $3$ and can be ruled out. The remaining cases are as follows.

Case 2: Four digits, namely $2$, $1$, $1$, $0$. The number must end in $1$ and start with $1$ or $2$. The possibilities are $1021$, $1201$, $2011$, and $2101$. The latter pair are ruled out because they are too large, but the former pair are both prime, as can be verified by testing against all primes less than $35$ (since, by the hint, $35 > \sqrt{1201}$).

Case 3: Four digits, namely $3$, $1$, $0$, $0$. The only possibilities are $1003$ and $3001$. Both are ruled out: the former is divisible by $17$, the latter is too big. In summary, we have exactly three solutions: $11$, $1021$, $1201$.