Given $a_0 > 1$, the sequence $a_0, a_1, a_2, ...$ is such that for all $k > 0$, $a_k$ is the smallest integer greater than $a_{k-1}$ which is relatively prime to all the earlier terms in the sequence.
Find all $a_0$ for which all terms of the sequence are primes or prime powers.
1. **Initial Setup and Definitions:**
   Given \( a_0 > 1 \), the sequence \( a_0, a_1, a_2, \ldots \) is defined such that for all \( k > 0 \), \( a_k \) is the smallest integer greater than \( a_{k-1} \) which is relatively prime to all the earlier terms in the sequence. We need to find all \( a_0 \) for which all terms of the sequence are primes or prime powers.

2. **Lemma 1:**
   Every prime divides a term in the sequence.
   - **Proof:** Take any prime \( p \). Suppose \( k \) is the least integer such that \( a_1 \le p^k \). Now let \( z \) be the least such integer such that \( a_z \ge p^k \). If \( a_z \neq p^k \), then \( p \) divides one of \( a_1, a_2, \ldots, a_{z-1} \). But then we're done.

3. **Corollary:**
   If \( p \) is prime, then \( p^{\lceil \log_p{a_1} \rceil} \) is one of the \( a_i \).

4. **Sequence Behavior:**
   It follows that for sufficiently large \( n \), the \( a_n \) are just a bunch of consecutive primes. Note that by the corollary, if \( a_n > a_0^2 \), then \( a_n \) is prime.

5. **Prime Product Argument:**
   We can pick two primes \( p \) and \( q \) such that \( pq \in [a_1, a_1^2] \) but \( p^{\lceil \log_p{a_1} \rceil}, q^{\lceil \log_q{a_1} \rceil} > pq \).
   - By Bertrand's Postulate, we can find a prime \( p \) such that \( \frac{\sqrt{a_1}}{2} - 1 < p < \sqrt{a_1} \) when \( a_1 \ge 16 \).
   - Let \( \frac{\sqrt{a_1}}{p} = z \). Then we can also find a prime \( q \) such that \( z\sqrt{a_1} < q < 2z\sqrt{a_1} \).

6. **Contradiction:**
   - Clearly, \( pq > a_1 \). However, \( p^{\lceil \log_p{a_1} \rceil} \ge p^3 > pq \).
   - We also have \( q^{\lceil \log_q{a_1} \rceil} = q^2 > pq \).
   - Thus, it follows that \( pq \) must be one of the \( a_i \), leading to a contradiction. Therefore, \( a_1 < 16 \).

7. **Case Analysis:**
   - Checking which values of \( a_1 \) less than 16 work involves casework.
   - Further analysis suggests that \( a_0 \) must be of the form \( 2^{2^n} \) except in some exceptional cases.

The final answer is \( \boxed{ a_0 } \) must be of the form \( 2^{2^n} \).