Is {a^n: n is a product of exactly two primes} regular? I am struggling to prove the following question.


  $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$


I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M &gt; m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| &gt; m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck.
I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.
Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.