Let $S$ be the set of all numbers that appear in the sequence $\{a_n\}_{n \ge 1}$. Since each number appears at most $5000$ times, for $N$ terms of the sequence, the number of distinct elements in $S$ is at least $N/5000$.

Suppose, for contradiction, that only finitely many primes divide the elements of $S$. Then all elements of $S$ are composed only of these finitely many primes, say $p_1, p_2, \dots, p_k$.

Thus, every $a_n$ is of the form $p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, where $\alpha_i \ge 0$ are integers.

Let $M = 1000^{1000^{\sqrt{\log_2 N}}}$, so $a_n \le M$ for $n \le N$.

The number of possible $a_n$ is at most the number of $k$-tuples $(\alpha_1, \dots, \alpha_k)$ such that $p_1^{\alpha_1} \cdots p_k^{\alpha_k} \le M$.

For each $i$, $\alpha_i \le \log_{p_i} M$. So the total number of possible $a_n$ is at most
$$\prod_{i=1}^k (1 + \log_{p_i} M) \le (1 + \log_2 M)^k$$
since $p_i \ge 2$.

But $\log_2 M = \log_2 (1000^{1000^{\sqrt{\log_2 N}}}) = 1000^{\sqrt{\log_2 N}} \cdot \log_2 1000$.

So $1 + \log_2 M \le 2 \cdot 1000^{\sqrt{\log_2 N}}$ for large $N$.

Therefore, the number of possible $a_n$ is at most $\left(2 \cdot 1000^{\sqrt{\log_2 N}}\right)^k$.

But the number of distinct $a_n$ among the first $N$ terms is at least $N/5000$.

So
$$\frac{N}{5000} \le \left(2 \cdot 1000^{\sqrt{\log_2 N}}\right)^k$$
Take logarithms:
$$\log_2 N - \log_2 5000 \le k \left(1 + \sqrt{\log_2 N} \cdot \log_2 1000\right)$$
For large $N$, $\log_2 N$ grows much faster than $\sqrt{\log_2 N}$, so for fixed $k$, this inequality fails for large $N$.

Therefore, our assumption that only finitely many primes divide the sequence is false.

Thus, there are infinitely many primes, each of which divides at least one member of the sequence.