Solution:
Suppose that $n$ has the required property. For every $j = 1, 2, \ldots, n$ denote by $q_{j}$ the least prime divisor of $a_{j}$ and let $q = \max_{1 \leq i \leq n} q_{i}$. Without loss of generality we may assume that $q = q_{1}$. Then
$$(3n+1)^{2} \geq a_{1} \geq q_{1}^{2} \geq p_{n}^{2}$$
where $p_{n}$ is the $n$-th prime number. Therefore we have $p_{n} \leq 3n+1$. It is easy to show (by induction) that $p_{n} > 3n+1$ for every $n \geq 15$. Hence $n \leq 14$. Since the set $\{2^{2}, 3^{2}, 5^{2}, \ldots, p_{14}^{2}\}$ has the required properties, we conclude that $n = 14$.