What is the Chomsky class of a language containing strings of a prime length? I recently saw a Perl golf program that used a perl regex in a loop in order to test primality. Perl's regex's are strictly more powerful the regular expressions and applying them in a loop can be used to basically create a turning machine. However it made me wonder. If you have a language $P = \\{ a^n : n \text{ is prime} \\} $ what class is it in? Now, since we can create a computer program to test primality, it is clear that $P$ is recursively enumerable. Also, the pumping lemma can show that the language is not regular. However I'm unsure if it could be context free or context sensitive.

Concerning the context-sensitiveness:

If the length is not prime, it has some divisor $k$. This means that you can write the string as $$a^k\cdot a^k \cdots a^k.$$ Checking this can be done in a tedious but straight-forward way (for $k$ from 2 to (half) the string's length) without exceeding the space that the original string occupies. Thus the language is context-sensitive.