Question and the examples
Examples: $n=16$, then we can swap $6$ and $1$ to get a prime $61$
$n=92$ , we can swap the digits to get the prime 29
What is the sufficient criteria for there to exist a rearrangement of a number's digit such that number becomes a prime? It may be quickly noted that numbers with all digits even are immediately disqualified.
A way to find total number of primes from permutation of a number $n$'s digits
Note: After googling, I found this method was just Sieve of Eratosthenes
If I have a number of length $n$, then I found an algorithm to find number of prime permutation of it's digits. I remove the permutations which are divisible by any number $k<n$ till I reach $n$.
For example if I have 12345, I have the set of numbers $\{1,2,3,4 ,5 \}$ for a total of 5! permutations, from which first I remove the numbers divisible by two, then three , then four, finally I add back the numbers divisible by two and four.
Related topics
There are the permutable primes, which are primes which stay prime independent of shuffling of digits. It is clear that this is a subset of the kind of numbers which satisfy the criteria in the question.
Best Answer
For some numbers, there are a few more clever obstructions. Base $10$ has the property that
So, the permutation of digits of any number that is a multiple of $3$ is disqualified from being prime.
There are a few other examples that fail: if a number has very few even digits, like $22\dots 212\dots 2$ for a lot of twos, there aren't that many ways to rearrange the digits so that the number isn't automatically disqualified from being prime due to being even (you can do the same with multiples of $5$, if you like). So, as long as $22\dots221$ isn't prime (and there's no reason to think it should be), there's no way to reorder its digits to make it prime.
The prime number theorem (very, very roughly) says that a number with $d$ digits has a "probability" of $\frac1{d\ln10}$ of being prime. (There are quotes around probability because this really doesn't make sense unless you're actually choosing a random number from a large enough interval; for more information on this notion, see this question). So, as long as the number of ways to reorder the digits of your number in a "not obviously not prime" way is a good bit larger than $d$, you should expect at least one of those reorderings to be prime. This is not a mathematically rigorous application of the prime number theorem, however, so it may be possible to find lots of numbers with many reorderings all of which are composite. This is likely not provable using current techniques.