Pumping Lemma for L = {a | k is a prime number}

  L = {a | k is a prime number}

Let us assume L is regular.  

-> Clearly L is infinite (there are infinitely many prime numbers). From the pumping lemma, there exists a number n such that any string w of length greater than n has a “repeatable” substring generating more strings in the language L.

Let us consider the first prime number p >= n.

For example, 

if n was 50 we could use p = 53. 

From the pumping lemma the string of length p has a “repeatable” substring. We will assume that this substring is of length k >= 1.

Hence:

It should be relatively clear that p + k, p + 2k, etc., cannot all be prime but let us add k p times, then we must have:

so this would imply that (k + 1)p is prime, which it is not since it is divisible by both p and k + 1. Hence L is not regular.