Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma
Let $L=\{a^p \mid p \in \text{Prime} \}$. 

Let $m,n\in\Bbb N$, $m&lt;n$. Let $s$ be the smallest prime number that is bigger than $(3n)! + 3n$. 


$a^na^{s-n}=a^s\in L$.
$a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n &lt; s - (n-m) &lt; s $. 


Any number between $(3n)! + 2n $ and $(3n)!+ 3n$ inclusive is not a prime number. 
Any number between $(3n)!+3n$ and $s$ exclusive is not a prime number.


So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.


The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.