Non-regularity of the set of primes in unary encoding using Myhill-Nerode
We can prove that every string in $L$, $a^p$, $p$ is prime, is in its own different equivalence class. We simply cannot have two strings, $a^p$ and $a^{p'}$, both $p$ and $p'$ prime, in same equivalence class. 

Assume $a^p$ and $a^q$, $q&gt;p$, $p$ and $q$ prime, are in same equivalence class. Then since $a^{p}a^{q-p}=a^q$ is in $L$ therefore $a^qa^{q-p}=a^{2q-p}$ will be in $L$. Since $a^{p}a^{2q-2p}=a^{2q-p}$ is in $L$ therefore $a^qa^{2q-2p}=a^{3q-2p}$ will be in $L$. We will be able to show that $a^{p+i(q-p)}$ will be in $L$ for every $i \geq 0 $. But for $i=p$ there is a contradiction.

Factually speaking even $a^c$ and $a^d$ for composites $c$ and $d$ will be in different equivalence classes. If we assume $a^c$ and $a^d$, $d &gt; c$, where $c$ and $d$ are not primes, are in same equivalence class, then we can similarly reach a contradiction. Even if we don't prove this, the number of equivalence classes is still infinite because each $a^p$ for prime $p$ is in different equivalence class.

Thus as number of equivalence classes for $L$ is infinite (because number of primes is infinite), therefore by Myhill-Nerode theorem $L$ is not a regular language.