Is C* regular if C is a language with strings of prime length?

Question

Let $C = \{a^p \ | \ p \ \text{is prime}\}$ be a language. I was able to show that $C$ is not regular using the pumping lemma.

However, I am having some trouble showing that $C^*$ is regular. Intuitively I believe it should be regular but I do not know how to construct a proof.

Any thoughts on how to do this one?

Answer 1

Hint: Try to find an explicit expression of $C^*$ in the form $$ C^* = \{a^n \mid n \in \text{fill in the right subset $A$ of $\mathbf N$ here}\} $$ By the very definition of the Kleene star, we have $$ A = \{n \in \mathbf N \mid n \text{ is a sum of prime numbers}\}$$ I'm sure you can find $A$, just think of $2$ and $3$, more primes are not needed.