Check if a NFA accepts a string of non-prime length
The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.
We can check whether the language accepted by an NFA is infinite as follows:

Remove all states which are unreachable form an initial state, or from which a final state cannot be reached.
Check whether the remaining graph contains a cycle.

If the language is infinite, you can immediately answer &quot;Yes&quot;. Otherwise, the NFA only accepts words of length at most $n-1$ (where $n$ is the number of states), and you can use the algorithm that you suggest. Your algorithm can be slightly optimized by identifying all letters in the alphabet.