# How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]

I want to show that the language $$L=\{a^p ~|~ p\text{ is not prime}\}$$ is not a CFL.

If I look at $$\bar{L}=\{a^p ~|~ p\text{ is prime}\}$$, it is pretty straightforward to show that it is not a CFL with the pumping lemma, by choosing the word $$w=a^p$$, and with $$w_{p+1}=a^{p+sp}=a^{p(1+s)}\notin L$$ because $$p(1+s)$$ is not a prime number.

But what word do I have to choose to prove that $$L$$ is not a CFL?

Thanks!

• Does this answer your question? Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem. Although the question is about regular languages, the proof in accepted answer also shows that $L$ is not context-free. Jun 19 at 16:17
• A unary language (a subset of $a^*$) is context-free iff it is regular. Jun 19 at 20:00
• @YuvalFilmus Interesting! Thank you! Jun 20 at 8:04