  We show that the set of prime numbers has exponential alternating complexity,
proving a conjecture by Fijalkow. We further show that the set of squarefree
integers has essentially maximal possible alternating complexity.
