Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$
Heres what I have:
"If Notprime were regular, then its complement would be regular also. However, the complement of Notprime is the language Prime, hence Notprime is non-regular."
Is this the right way of proving it? Any help is appreciated!
This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).
The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.
For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.
