Suppose the statement is true, and this langauge is regular. Then there exists a FSA(finite state automaton) that recognizes this language, which we call M. The pumping lemma says that there exists a natural number p such that for every string s in L(M) of length at least p, there is a decompositon of s=xyz such

that:

|y| > 0

|xy| <= p

Now, we can assume that there is a string w in L(M) such that |w|=k is the first prime number greater than p since there are infinitely many prime numbers. Because w is in L(M) and |w| > p, w can be decomposed as w=xyz that satisfies the above conditions.

Now consider the string . By the condition 3 above, v is in L(M). Thus, the length of v must be a prime number. But . Clearly, k | k(1+|y|) and k > 1. Hence |v| is not prime. This contradiction implies that the supposition is false, and the given langauge is not regular.